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. In other words, you are given a set of n numbers which you must partition into as few subsets as possible with the requirement that each subset should sum up to at most 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. This would get the weights .1 .3 .7 .8 into two bins.
Write a program that implements these heuristics in an efficient manner to find out how many bins are required for a
random sequence of N weights in the range 0 to u, using a heap. Your task is to
write two programs, one for each of the two heuristics. Your
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.
Extra Credit. Find a heuristic that beats worst-fit and worst-fit decreasing
consistently for N=10000.
Due: Thursday, February 24, at 11:59pm.