Data Structures and Problem Solving Using Java 4th edition

exercise 21.25

Suppose that you have a number of boxes, each of which can hold total weight 1.0 and items i1, i2, i3, ..., iN, which weigh w1, w2, w3, ..., wN, respectively. The object is to pack all the items, using as few boxes as possible, without placing more weight in any box than its capacity. For instance, if the items have weights 0.4, 0.4, 0.6, and 0.6, you can solve the problem with two boxes. This problem is dif?cult, and no ef?cient algorithm is known. Several strategies give good, but not optimal, packings. Write programs to implement ef?ciently the following approximation strategies. a. Scan the items in the order given; place each new item in the most-?lled box that can accept it without over?owing. Use a priority queue to determine the box that an item goes in. b. Sort the items, placing the heaviest item ?rst; then use the strategy in part (a).