Items are (weight, value) pairs (5,10), (4,40), (6,30), (3,50) and the capacity is 10. Give the optimal value for the 0/1 knapsack and for the unbounded version, and state the single change in the loop order that converts one dynamic program into the other.

Items are (weight, value) pairs (5,10), (4,40), (6,30), (3,50) and the capacity is 10. Give the optimal value for the 0/1 knapsack and for the unbounded version, and state the single change in the loop order that converts one dynamic program into the other.

Approach: Fill a one-dimensional table indexed by capacity. The direction of the inner loop decides whether an item can be reused within the same pass.

90 for 0/1 and 150 for unbounded. For 0/1, the pair (4,40) and (3,50) uses weight 7 for value 90, and every other feasible set is worse: (6,30) with (3,50) gives 80, (6,30) with (4,40) gives 70, and (5,10) never helps. For the unbounded knapsack, three copies of (3,50) use weight 9 for value 150, which beats two copies plus (4,40) at 140. In the one-dimensional formulation dp[c] = max(dp[c], dp[c - w] + v), the loop direction decides everything: iterating the capacity downward from the maximum means dp[c - w] still refers to the table before this item was considered, so each item is used at most once. Iterating upward means dp[c - w] may already include a copy of the same item, which is exactly the item reuse the unbounded version wants. Both run in O(n * C) time and O(C) space, which is pseudo-polynomial since C is exponential in the number of bits used to write the capacity.

Follow-up: How do you recover the chosen items in the one-dimensional formulation without storing the full table?

Key concepts: knapsack, capacity table, loop direction, item reuse.