Bin-packing is a classic computer science problem with many real-world applications. The idea is to fit items with some characteristic like weight or size into containers called bins so as to minimize the number of bins. In the version of the problem you will work on the items being fit or packed are files --- these files are specified by their size. You can think of the files as mp3 files or video files. Their size is given in kbytes, so a file size of 420713 represents about 420 MB (Megabytes) which is a little less than half a Gigabyte or GB.
The bins are disks. You can think of them as CDs or DVDs and you're trying to minimize the number of disks used to contain all the files being fit or packed. In this problem each disk has a capacity of 1 GB, or 1,000 MB.
The input to the program is a file of file-sizes. The output is specified below --- a report of the total of all the file sizes in GB and the number of disks used to store all the files.
You will implement two worst-fit heuristics: in-order and in-decreasing-order. In general, worst-fit heuristics store a each file on the disk with the most free-space. If there is no disk with enough free-space, another disk is started. For in-order, the files are examined in the order in which they are given. For worst-fit decreasing, are examined in sorted order from the largest file-size first continuing to the smallest file-size.
For example, if the file sizes given are
700,000 200,000 800,000 100,000 150,000
then, using the worst-fit in-order heuristic, the following three disks will be used to store the files
700,000 200,000 800,000 100,000 150,000
Using the worst-fit in-order heuristic, the same data above will yield the following two disks (which happens to be the minimum)
800,000 150,000 700,000 200,000 100,000
The following output shows the disks created from this input file of 20 file sizes (from the Princeton assignment) using both worst-fit heuristics.
total size = 6.581 GB in-order worst-fit heuristic # disks used = 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 in-decreasing-order worst-fit heuristic # disks used = 7 1 211686: 396295 392019 0 94485: 484802 420713 6 47762: 262926 254274 230973 204065 5 44188: 324387 320414 311011 3 18470: 347661 347560 286309 4 1413: 340190 331812 326585 2 1000: 383972 351543 263485
To find the disk with the most free-space, keep the disks in sorted order according to their free space, such that the first disk in the collection is always the one with the greatest amount of free space (a priority queue maintains its elements in such order).
Here is example code that will read a file of file-sizes and insert/create disks using a priority queue. Note, this code essentially implements the worst-fit in-order heuristic.
public static void main (String args[]) { PriorityQueue<Disk> pq = new PriorityQueue<Disk>(); int diskId = 0; Disk d = new Disk(diskId); pq.add(d); int size; double total = 0.0; Scanner input = new Scanner(); while (input.hasNext()) { size = input.nextInt(); total += size/1000.0; d = pq.peek(); if (d.freeSpace() >= size) { pq.poll(); d.add(size); pq.add(d); } else { diskId++; Disk d2 = new Disk(diskId); d2.add(size); pq.add(d2); } // rest of code omitted ... }
In addition to implementing the remaining heuristic and generating output similar to what was shown above, you should implement the class Disk such that it supports the code shown above.