Solutions to Assignment #2, CS 155, Section 1, Fall 2007

Solutions to Assignment #2, CS 155, Section 1

October 4, 2007

For the capacity 13 case, the algorithm will construct (perhaps implicitly) the following table:
```
   0 0 0 10 10 10 10 10 10 10 10 10 10 10 
   0 0 0 10 13 13 13 23 23 23 23 23 23 23 
   0 0 0 10 13 13 18 23 23 28 31 31 31 41 
   0 0 0 10 13 14 18 23 24 28 31 32 37 41 
   0 0 0 10 13 14 18 23 24 28 31 32 37 41 
```
For the smaller capacities, it will construct only as much of this table as is needed. The values of the solutions for capacities 9 through 13 can be seen to be 28, 31, 32, 37, and 41. The respective solutions are those that include items of the following weights: 6 and 3; 6 and 4; 6 and 5; 5, 3, and 4; and 6, 3, and 4.
The values of the optimal solutions are 313, 332, 348, and 363. All four solutions include the 6 items of highest profit density (those of weights 7, 8, 14, 13, 9, and 11). These items have a combined weight of 62 and benefit 249.
The capacity 80 solution would also include the items of weight 6 and 12, and benefits 22 and 42. The capacity 85 solution would also include the items of weight 4, 6, 3 and 10, and benefits 15, 22, 11, and 35. The capacity 90 solution would also include the items of weight 6, 12, and 10, and benefits 22, 42, and 35. The capacity 95 solution would also include the weight 6, 12, 10, and 4, and benefits 22, 42, 35, and 15. Note that this last solution does not fill the knapsack.

The tree given below is appropriate for a capacity of 13. For the smaller capacities, more nodes could be pruned. In the tree, an asterisk represents a case of overflow, a caret represents information that is the same as the parent, and bold face represents an exact filling (for which children needn't be generated). For other nodes, the weight and benefit of the current partial filling is shown. Note that the solutions for the smaller capacities all appear in the tree.

                             0/0
              /                                    \
         6/18                                       ^
     /           \                        /                     \
11/32             ^                   5/14                       ^
 /\           /       \             /      \               /           \
*  ^      9/28         ^        8/24        ^          3/10             ^
  / \     / \        /   \       / \      /   \        /   \          /   \ 
 *  ^  13/41 ^  10/31     ^  12/37 ^  9/27     ^   7/23     ^     4/13     ^
   / \      / \  / \     / \  / \ / \ / \     / \  / \     / \     / \    / \
   * ^      * ^  * ^ 13/35 ^  * ^ * ^ * ^ 12/31 ^  * ^ 10/27 ^ 11/30 ^ 7/17 ^

The optimal solutions are given in the answer to #2.
After sorting, the weight sequence becomes (3, 4, 6, 5, 7) and the profit sequence becomes (10, 13, 18, 14, 17). In each case, all of the first two items may be included. For capacities 9, 10, 11, and 12, the algorithm will include respectively 1/3, 1/2, 2/3, and 5/6 of item 3, and then terminate. For capacity 13, it will include all of item 3 and then terminate. For capacity 25, all items will be included with full weight.
The weight and profit sequences after sorting are given above. For capacities 9, 10, and 11, the algorithm will include the first two items only. For capacity 12, it will also include the fourth item. For capacity 13, it will add the third item instead of the fourth item. For capacity 25, it will include all items.
Suppose that there was such a constant c, and consider the instance with capacity c+2 and two items, one of weight and benefit 1, and the other of weight c+2 and benefit c+1. The first item has higher profit density, so the greedy algorithm would return a solution of total benefit 1. But the optimal solution includes only the second item and has a total benefit of c+1, which is greater than c. Here the optimal solution has value more than c times the value of the greedy solution, in contradiction to our assumption.
One possible instance would have capacity 21, two items of weight 10 and benefit 101, and three items of weight 7 and benefit 70. The two items of weight 10 have the highest profit density, but the only optimal solution includes the three items of weight 7, for a total benefit of 210. Note that there is room in the knapsack for both items of weight 10, but that they contribute a combined benefit of only 202.