A knapsack with capacity 8 is filled with items chosen from four items with (weight, value) of (2, 3), (3, 4), (4, 5) and (5, 6). There is only one of each item and items cannot be split. What is the maximum total value with a total weight of 8 or less?

Answer: C. 10

Choosing the items of weight 3 and 5 gives weight 8 and value 4 + 6 = 10, which is the maximum. Weights 2 and 5 (value 9) or 3 and 4 (value 9) also fit but fall short of 10, and any three items weigh at least 2 + 3 + 4 = 9, over the capacity. A greedy algorithm that packs items in order of value per unit weight takes the items of weight 2 and 3 (value 7), and then no item fits in the remaining capacity of 3, so it stops at 7. Dynamic programming updates a table of the best value achievable within each capacity c item by item, and finds the optimum in O(nW) for n items and capacity W.

• A. This is the result of a greedy algorithm that packs by value per unit weight, which is not optimal.
• B. This is the value of weights 2 and 5, or 3 and 4, which is not the maximum.
• C. Correct. The items of weight 3 and 5 use the capacity of 8 exactly and give a value of 10.