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

23 Solutions
6 Solvers

Last Solution submitted on Jun 16, 2018

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 Solvers6

Problem Tags

contest cumsum optimization

Problem 1161. Binpack Contest: Retro

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers6

Suggested Problems

More from this Author236

Problem Tags

Problem 1161. Binpack Contest: Retro

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers6

Suggested Problems

More from this Author236

Problem Tags

Players