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.
Your client programs should take N and u as
command-line arguments so that, for example, java Assign6 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.
You can use java.util.Random class to get some random numbers
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.
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.