Question: 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 difficult, and no efficient algorithm is known. Several strategies give good, but not optimal, packings. Write programs to implement efficiently the following approximation strategies.
a. Scan the items in the order given; place each new item in the most-filled box that can accept it without overflowing. Use a priority queue to determine the box that an item goes in.
b. Sort the items, placing the heaviest item first; then use the strategy in part (a).