BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 964

objects and the weight of each object. The program displays the total number of
containers needed to pack the objects and the contents of each container. Here
is a sample run of the program:

Enter the number of objects: 6
Enter the weights of the objects: 7 5 2 3 5 8
Container 1 contains objects with weight 7 2
Container 2 contains objects with weight 5 3
Container 3 contains objects with weight 5
Container 4 contains objects with weight 8

Does this program produce an optimal solution, that is, finding the minimum
number of containers to pack the objects?

25.21

( Bin packing with smallest object first ) Rewrite the preceding program that uses
a new greedy algorithm that places an object with the smallest weight into the
first bin in which it would fit. Your program should prompt the user to enter the
total number of objects and the weight of each object. The program displays the
total number of containers needed to pack the objects and the contents of each
container. Here is a sample run of the program:

Enter the number of objects: 6
Enter the weights of the objects: 7 5 2 3 5 8
Container 1 contains objects with weight 2 3 5
Container 2 contains objects with weight 5
Container 3 contains objects with weight 7
Container 4 contains objects with weight 8

Does this program produce an optimal solution, that is, finding the minimum
number of containers to pack the objects?

25.22

( Bin packing with largest object first ) Rewrite the preceding program that places
an object with the largest weight into the first bin in which it would fit. Give an
example to show that this program does not produce an optimal solution.

25.23

( Optimal bin packing ) Rewrite the preceding program so that it finds an optimal
solution that packs all objects using the smallest number of containers . Here is
a sample run of the program:

Enter the number of objects: 6
Enter the weights of the objects: 7 5 2 3 5 8
Container 1 contains objects with weight 7 3
Container 2 contains objects with weight 5 5
Container 3 contains objects with weight 2 8
The optimal number of bins is 3

What is the time complexity of your program?