We formulate the bin packing problem as follows: given a set of N file sizes between 0 and 1,000,000 KB (1 GB), find a way to assign them to a minimal number of disks, each of capacity 1 GB. Two intuitive heuristics immediately spring to mind. The worst-fit heuristic is to consider the file sizes in the order they are presented: if the sound file won't fit on any disk, create a new disk; otherwise place the file on a disk that has the most remaining space. For example, this algorithm would put the sizes 700,000, 800,000, 200,000, 150,000, 150,000 onto three disks: {700,000, 200,000}, {800,000, 150,000}, {150,000}. The best-fit heuristic is identical, except that the file is placed on a disk that has the least space among all disks with enough room to store the file. This algorithm would put the same sequence of weights onto two disks: {800,000, 200,000}, {700,000, 150,000, 150,000}.
Your task is to implement the two heuristics and compare their performance.
Perspective. The bin packing problem is a fundamental problem for minimizing the consumption of a scarce resource, usually space. Applications include: packing the data for Internet phone calls into ATM packets, optimizing file storage on removable media, assigning commercials to station breaks, allocating computer memory, and minimizing the number of identical processors needed to process a set of tasks by a given deadline. In the latter example, the scarce resource is time instead of space. Cloth, paper, and sheet metal manufacturers use a two-dimensional version of the problem to optimally cut pieces of material (according to customer demand) from standard sized rectangular sheets. Shipping companies use a three-dimensional version to optimally pack containers or trucks.
Item data type. To use the priority queue and symbol table ADTs, you need to specify and implement an appropriate Item data type to represent the disks. In addition to a list of the file sizes, this data type should contain a key field for use with a priority queue or symbol table ADT. The files item.h and item.c provide a sample interface and implementation of the Item data type for ints. One of your challenges is to rewrite these two files to be useful in your file storing applications. This will require some thought (and perhaps a few iterations on the problem). You must use the same Item data type in both of your heuristics.
Priority queue and symbol table ADTs. For each of the two basic heuristics (worst-fit and best-fit), you will need to develop an efficient data structure that supports all of the basic operations needed to implement that heuristic. You are required to implement each of your heuristics using the client-implementation-interface paradigm.
For the worst-fit heuristic, create an interface pq.h that specifies which operations your data structure will support. You will certainly need insert and delete the maximum, so a priority queue seems like a judicious starting point. Create a file pq.c that implements these operations and a client program worstfit.c that uses these operations to perform the worst-fit heuristic. As a starting point, you may use this priority queue implementation and interface. They are adaptions of the heap code in Sedgewick Program 9.2. You are free to add functionality to the interface and implementation to support the client.
For the best-fit heuristic, create an interface st.h that specifies which operations you will need to support the best-fit heuristic. You will certainly need an insert operation. You will also need an efficient way to find the most full disk among those that still have enough room to store a given file size. Implementing this will require some careful thought and design. Create a file st.c that implements these operations and a client program bestfit.c that uses these operations to perform the best-fit heuristic. You might start by implementing a brute force solution, but you will quickly see that this approach is too slow to be useful in practice. Binary search trees provide more flexibility than heaps, so consider using and extending the following symbol table implementation and interface. They are adaptions of the randomized binary search tree code in Sedgewick Programs 13.2-13.4.
Input and output.
Your client program will read in the set of file sizes (guaranteed to be
between zero and a million) from standard input.
Your program should output the number of disks used by the heuristic and
the sum of all file sizes divided by 1 million (a lower bound on
the number of disks required).
If the number of files is less than 100, you should also print out the
disks in decreasing order of remaining space.
For each disk, print out the amount of remaining space and the file sizes that
it includes (in the order that they were inserted). For debugging, the output
below also includes a unique id number (optional) for each disk that represents
the order in which the disk was created.
% worstfit < input20.txt
file sizes sum = 6.58 GB
total disks = 8
5 325754: 347661 326585
0 227744: 420713 351543
7 224009: 383972 392019
4 190811: 324387 484802
6 142051: 340190 263485 254274
3 116563: 347560 204065 331812
2 109806: 396295 230973 262926
1 82266: 311011 286309 320414
Worst-fit decreasing and best-fit decreasing. Experienced travelers know that if small items are packed last, they can fit snugly in the odd gaps in nearly filled luggage. This motivates a smarter strategy: process the items from biggest to smallest. The worst-fit decreasing heuristic is to do worst-fit, but first preprocess the file sizes so that they are in descending order. The best-fit decreasing heuristic is define analogously.
Don't write any extra code to implement the worst- and best-fit decreasing heuristics. Instead, sort the input file in descending order using an independent sorting routine, then pipe the results through your best-fit heuristic. You can accomplish this in Unix with:
or from the Windows command prompt with:% gcc bestfit.c st.c item.c -o bestfit % sort -r < input20.txt | bestfit
C:\> lcc bestfit.c st.c item.c C:\> sort /r < input20.txt | bestfit
Analysis. Run your heuristics on a variety of inputs, with N = 100, 1,000, 10,000, 100,000, and 1,000,000. Do a few trials for each value of N using random weights between zero and one million. In your writeup, comment on the relative effectiveness (number of disks used) of the four heuristics (best-fit, worst-fit, and the decreasing variants).
Extra Credit.
Design and implement a heuristic that consistently beats best-fit decreasing
for N =100,000.