CPS 100, Spring 2004, Bin-packing

The concept for this assignment is taken from COS 226 at Princeton

Overview

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'll 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 --- you print the total of all the file sizes in GB (use a double, the files get big fast) and the number of disks used to store all the files. For part I of the assignment you'll be designing the class Disk to store files so that Disk objects can be inserted and deleted from a priority queue.

Heuristics

You'll implement two-heuristics: worst-fit and worst-fit decreasing. The idea of the worst-fit heuristic is to store a file on the disk with the most free-space. If there is no disk with enough free-space, start another disk. You store files in the order in which they're read by your program.

To find the disk with the most free-space, you'll keep the disks in a priority queue whose getmin/deletemin method will return the disk with the greatest amount of free-space. Here's the code that will read a file of file-sizes and insert/create disks using a priority queue.

int main() { tpqueue<Disk> pq; int diskId = 0; Disk d(diskId); pq.insert(d); int size; double total = 0.0; while (input >> size){ total += size/1000.0; d = pq.getmin(); if (d.freeSpace() >= size){ pq.deletemin(d); d.add(size); pq.insert(d); } else { Disk d2(diskId); diskId++; d2.add(size); pq.insert(d2); } } // all file-sizes read, priority queue holds all disks

For example, if the file sizes are

  700,000   200,000   800,000   100,000   150,000

then the disks created will store files as follows:

   700,000  200,000
   800,000  100,000
   150,000

for a total of 3 disks used to store nearly 2Gb of data.

For worst-fit decreasing you simply read all the file-sizes into a vector, sort the vector from largest to smallest, and then insert the largest file-size first continuing until the last item inserted is the smallest file-size.

Using this heuristic the same data above that yields 3 disks with worst-fit will yield the following two disks (rememember the file-sizes are now sorted before insertion/disk creation) which is the minimum.

  800,000  150,000
  700,000  200,000   100,000

What to do First

Disk. You may need to review how the tpqueue class works, you can see pqdemo code for help.

The class should support the code shown above, and should support generating output similar to what's shown below that shows the disks created from this input file of 20 file sizes (from the Princeton assignment).


total size = 6.581 GB
# 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

Design the public and private sections of the class Disk and think about how to implement the methods you specify. Write the .h file for the class.

Owen L. Astrachan

Last modified: Fri Mar 19 09:04:40 EST 2004