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 };
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.