COS 226 Programming Assignment Checklist: Bin Packing

Goals

Here are the main goals of the assignment.

Frequently Asked Questions

My program doesn't compile when I hit the Compile button on the Web submission system. Is this OK? No. You will lose a substantial number of points if you don't follow the instructions.

Do I need to use a binary heap? No, that's just a suggestion, but probably a good one. However, you should be able to handle the large instances (a million weights).

Can I use the Java library LinkedList or ArrayList to store the files associated with each disk? Yes, and you are encouraged to use Java's foreach syntax to iterate through the elements when printing them out.

Am I required to format the list of file sizes exactly as in the reference solution? No, this is not a requirement. For C programmers, Java 1.5 contains methods System.out.printf and String.format that work much like printf.

Input, Output, and Testing

Input.   Your program should read in a sequence of integers between 0 and 1000000 separated by whitespace from standard input. Here are some sample input files. You may also use Generator.java to generate random test instances. It takes 3 command line inputs N, L, and U, and generates N pseudorandom integers between L and U.

Reference solutions.   For reference, we provide our executable code for the two heuristics on Windows, Solaris, and OS X. Choose the version of worstfit226 for your operating system and execute with worstfit226 < input.txt. Note that these programs were written in C, so you may see slightly different behavior, e.g., the formatting of the numbers. Also, the priority queue is not "stable", so although the remaining capacities of all the disk should match, you may get different file sizes on some disks.

readme.txt

You may use the following readme file template. Besides providing details about your implementation which are not clear from the comments within your source code, your readme.txt file should also contain:

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

Enrichment Section

Researchers have proved some amazing things about bin packing heuristics. For example, if the optimal packing uses B bins then the best-fit decreasing algorithm is guaranteed to use no more than 11B/9 + 1 bins (within 22% of best possible). The original proof of this result (for the first-fit decreasing heuristic) required over 70 pages of analysis! The file worstcase30.txt gives a worst-case instance where the best-fit decreasing algorithm uses 11 bins even though the weights fit snugly into 9 bins.