Rules

The Challenge

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.

Problem

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 Song Lists and Entries

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.

Judging Criteria

Note: you are not required to find the optimal solution!

There are two criteria for the judging of this contest:

• the gap, time remaining at the end of the CD, i.e.
  gap = (mediaLength - sum(songList(indexList))) ---------------------------------------- mediaLength
• the execution time of the algorithm.

    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:

1. Each song may be used zero or one times in the play list.
2. Do not exceed the target time mediaLength.
3. Return valid answers for the test suite in 90 seconds or less.
4. The entry must run without error in MATLAB version 5.2. Other toolbox functions will not be available.
5. Some standard MATLAB functions have also been disabled for this contest. See the fine print below for details.

Deadline

Editing Existing Entries

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.

Prizes

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.

Fine Print

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:

• MEX-files
• eval, feval, etc.
• Shell escape such as !, dos, unix
• Handle Graphics commands
• ActiveX commands
• File I/O commands
• Debugging commands
• Printing commands
• Simulink commands
• Benchmark commands such as tic, toc, and flops

For More Information

Please send any comments or questions to the MATLAB Programming Contest.