Write an application that performs bin packing: The input consists of a sequence of
packages'' whose sizes are coded as nonnegative integers along with a sequence of bins” whose capacities are are coded also by an integer. (For simplicity, we assume that all bins have the same capacity.) The program assigns each package to a bin such that no bin’s capacity is exceeded. The objective is to use the minimum number of bins to hold all the packages. Attempt these implementations:
- Smallest packages first: The packages are sorted by size and smallest packages are used first.
- Largest packages first: The packages are sorted by size and largest packages are used first.
- Random filling: The packages are used in the order they appear in the input.
(Hint: read the Supplement section on sorting.)
After you have implemented all three programs, perform case studies to determine when one strategy performs better than another. This problem is famous because there is no efficient algorithm for best filling the bins.