Problem 1161. Binpack Contest: Retro

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/contest/contests/3/rules\"><w:r><w:t>Full Binpack Rules and examples</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is a replay opportunity of the First Matlab Contest, 1998 BinPack.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Brief Challenge statement: Pack a 45(mediaLength) minute CD as maximally as possible given a list of songs of varying lengths. No penalty for unused songs. No song duplication allowed. Return the indices of the songs used.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [songList, mediaLength]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> indexList</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input: [ 0.5 2 3 1.5 4], [5.6]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output: [4 5] as 1.5+4 is very near and below 5.6.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The answer of [1 2 3] is also valid and also gives 5.5.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Scoring:</w:t></w:r><w:r><w:t> 150*Gap/(12*45)+Time*3 (cases are repeated 100 times to get a time)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Warning:</w:t></w:r><w:r><w:t> Matlab 2013B may produce time slowing error messages versus 1998 code.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

25 Solutions
8 Solvers

Last Solution submitted on Sep 28, 2021

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

trekker on 2 Jan 2013

the test cases provided are too large for the server to handle.

Richard Zapor on 3 Jan 2013

Running the 12 cases 100 times each consumes only .52 seconds. Part of Challenge is managing depth of search. Perfect does not exist.

trekker on 3 Jan 2013

got your point. Only .52 sec for 12 cases 100 times? wow.

Richard Zapor on 3 Jan 2013

Usage of bintprog. I see per ver that Optimization Toolbox exists but a little digging gave Error: License checkout failed.
License Manager Error -5

Problem Recent Solvers8

Problem Tags

contest cumsum optimization

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1161. Binpack Contest: Retro

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author255

Problem Tags

Community Treasure Hunt

Problem 1161. Binpack Contest: Retro

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author255

Problem Tags

Community Treasure Hunt

Players