|
|
Print the bins in decreasing order or remaining space when N is small. This should be easier.
|
|
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. We will compile your programs with the following commands:
Even if you don't use priority queues or symbol tables, use these file names or risk angering your grader!gcc worstfit.c pq.c item.c gcc bestfit.c st.c item.c
Do I need to use a heap or binary search tree? No, that's just a suggestion (but probably a good one). However, you should be able to handle the large instances (a million weights).
With the data file input5.txt (and others), my computer believes that the three values 0.7, 0.15, and 0.15 sum to a value greater than 1.0. What is going on? Your program should only need 1 bin to store these three values. You are encountering common issues involving the representation of real numbers on binary computers. To effectively handle double precision numbers, you should define a constant, say EPS = 0.00000001, and modify your comparison functions so that a bin can store weight up to 1.0 + EPS.
My program prints -0.000000. What is this? It a very small negative number that when truncated looks like -0. Again, floating-point precision is the culprit.
|
|
Input. Your program should read in a sequence of real numbers between 0.0 and 1.0 separated by whitespace from standard input. Here are some sample input files. You may also use generator.c to generate random test instances. It takes 4 command line inputs N, l, u, and s and generate N pseudorandom real numbers between l and u using the seed s. The fourth command line input is optional: if it is not supplied the seed is set arbitrarily via the system clock.
Reference solutions. For reference, we provide our executable code for the two heuristics on Windows, Solaris, and OS X.
|
|
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:
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
|
|
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.