Assignment #6: Bin Packing

Solve the ``bin packing'' problem: Given a set of weights (each between 0 and 1), the bin packing problem is to find a way to assign the weights to a minimal number of bins of capacity 1. This problem is difficult to solve in general, so a number of heuristics have been studied. The ``worst fit'' heuristic is to consider the weights in the order they are presented: if the weight won't fit in any bin, create a new bin, otherwise place the weight in the bin that has the most space. For example, this algorithm would put the weights .1 .3 .7 .8 into three bins (note that this is not the best possible solution). The ``worst fit decreasing'' heuristic is to do worst-fit, but with the weights in decreasing order (in other words, begin with a preprocessing step that sorts the items, largest first). This would get the weights .1 .3 .7 .8 into two bins.

Write a program that implements these heurisitics in an efficient manner to find out how many bins are required for a random (uniformly distributed) sequence of N weights in the range 0 to u, using a priority queue ADT. Your client programs should take N and u as command-line arguments so that, for example, a.out 100 .2 will generate 100 random weights between 0 and .2 and print out the total of the weights generated (best possible number of bins) and the number of bins resulting from applying the heuristic.

In addition to printing out the number of bins used, if N is less than or equal to 20, print out the weights generated and the contents of the bins in some reasonable format. Note that your program should be keeping track of the bin contents no matter what; it is just that these contents are printed only if N is sufficiently small.

Your code will declare a priority queue (BinaryHeap) of Bins. Each Bin keeps track of its contents; note that to avoid excessive copying, the Vector will be stored with shallow semantics. I would expect to see something along these lines (I will discuss in class on Nov 16; if you miss class, get someone's notes.):

class Bin
{
  public:
    Bin( int id = 0, double FirstItem = 0.0 ); // Constructor
    void AddItem( double X );                  // Add new item of size X
    void Print( ostream & Out = cout ) const;  // Print bin contents
    void Dispose( );                           // Cleanup the Vector
    bool operator<( const Bin & Rhs ) const;   // Comparison function
    // Other stuff as you see fit
    
  private:
    int ID;     // The bin identifier (each bin gets a new one).
    double HowFull;  // How full the bin currently is; ranges from 0 to 1
    Vector<double> *Contents;  // The contents of the bin; note shallowness
};

Available Code

You can use atoi and atof to convert the argv parameters to the numeric types. You may use the BinaryHeap class that is available online (do not use the Toss function). If you want, you can use the STL instead, but if you do, you have to learn that part of the STL your own (you may not use a set because of the possibility of duplicates). You may use the revised code from the newer book. You may use any compiler.

You can also use the Random class to get some random numbers (see Chapter 9, or just look at Random.h). To generate a uniformly distributed random number between 0 and u, generate one between 0 and 1, and multiply it by u.

What to Submit

Submit your source code (you do not have to submit the binary heap or random classes). Run both algorithms for N= 20, 200, 2000, 20000, and 200000. Do a few trials for each value with u=.25 and u=.75. Make sure each trial uses a different set of random numbers. In otherwords, the inital seed for the random number generator should vary between runs. Give output and include a brief writeup that comments on the relative effectiveness of the two heuristics.

Due Date

This assignment is due on Monday, November 30.