Winner Hakan Erdogan (cumsumshortsort)
You work for a large record company that markets a line of greatest hits compact discs --- "70's Super Funk", "Partridge Family Unlimited", "Three Tenors in Antarctica, Again!". For each CD, you have a list of possible songs, their lengths, and the CD's maximum length.
You would like each CD to be as close to full as possible, but you have a large catalog of CD's to fill, in anticipation of an 80's revival. It's okay to leave a bit of empty space on each CD to get the job done quickly. You have decided to use MATLAB to determine the set of songs for each CD.
You will be provided with a list, in vector form, of song times, and the length of a CD. Not all the songs will fit on the CD. Your job is to return a single vector of indices into that vector of the songs you have chosen for this CD.
The sum of the song times that you select should not be greater than the provided media length. You need not use all of the provided songs; there may be more songs than you have space for on a single CD. There were a lot of great disco songs, but you only want to produce a single disco CD.
In MATLAB syntax, the function header should look like this:
function indexList = binpack(songList, mediaLength)
More precisely, given a vector of arbitrary length, songList
, find a vector of indices, indexList,
such that
sum(songList(indexList)) <= mediaLength
, and
gap = (mediaLength - sum(songList(indexList))) / mediaLength
is minimized.
Example:
If |
Example songlists are
available. Use mediaLength = 45
with these examples.
An example entry is also available. This function is listed in the rankings as the entry BINPACK EXAMPLE by contest@mathworks.com.
Note: you are not required to find the optimal solution!
There are two criteria for the judging of this contest:
gap =
(mediaLength - sum(songList(indexList)))
----------------------------------------
mediaLength
score = gap * (time + alpha)
where alpha is 0.018 sec to increase the relative importance of the gap measure. This ensures that a very fast, very stupid entry with zero time but with awful performance does not win.
We will run your algorithm through a suite of tests. We will measure CPU time and the gap for each test point, to score the entry for each test point. The winning entry is the one with the lowest average score over the test suite.
Your only strict requirements are:
mediaLength
.Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and modify any entries in the queue. The contest server maintains a history for each modified entry. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.
The final author of the winning entry will receive a CD of the greatest hits of the 70's and a MATLAB denim shirt. To encourage collaboration, the judges will acknowledge every significant contributor to the winning entry.
Winning entries must be original or must be substantial improvements on other entries. The contest administrators reserve the right to disqualify trivial changes.
Tip: You can use the which
function to check whether a function you would like to use is part of a toolbox or part of the standard MATLAB distribution.
The following are prohibited:
Please send any comments or questions to the MATLAB Programming Contest.
Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest: