A knapsack has capacity 10. Three items are available: Item A (weight=6, value=8), Item B (weight=5, value=5), Item C (weight=5, value=5). A greedy algorithm selects items by highest value-to-weight ratio first. What does the greedy algorithm choose, and what is the optimal selection?
AGreedy: Item A (value=8); Optimal: Items B and C (value=10)
BGreedy: Items B and C (value=10); Optimal: Item A (value=8)
CGreedy: Item A (value=8); Optimal: Item A (value=8)
DGreedy: Items B and C (value=10); Optimal: Items B and C (value=10)
Item A's value-to-weight ratio is 8/6 ≈ 1.33, higher than B or C (1.0 each), so greedy selects A first (total value 8, weight 6). With 4 units of capacity remaining, neither B nor C fits. But selecting B and C uses exactly 10 units of capacity and yields value 10, which is better. This is the core failure of greedy for 0/1 knapsack: the all-or-nothing constraint means that filling capacity with the highest-ratio item may leave insufficient room for combinations of smaller items that total more value.
Question 2 Multiple Choice
After filling a 2D dp[n][W] table for the 0/1 knapsack, how do you determine which items were included in the optimal solution?
ASelect the n items whose individual values appear in the dp table cells
BTrace backward from dp[n][W]: if dp[i][w] ≠ dp[i-1][w], item i was included; move to dp[i-1][w - weight_i]
CRe-run the greedy algorithm on the items sorted by their DP-table contributions
DRead the items off the final row of the table in left-to-right order
The DP table stores optimal values, not item selections. To reconstruct the solution, you backtrack: starting at dp[n][W], if the value differs from dp[i-1][w], item i was included (because we took the 'include' branch in the recurrence). Record item i, subtract its weight, and move to dp[i-1][w - weight_i]. If the values are equal, item i was skipped — just move to dp[i-1][w]. This linear-time reconstruction is a key step that distinguishes computing the optimal value from recovering the optimal subset.
Question 3 True / False
The 1D (space-optimized) version of the 0/1 knapsack DP requires iterating through capacity values in decreasing order (from W down to weight_i) when processing each item.
TTrue
FFalse
Answer: True
In the standard 2D recurrence, the 'include item i' case reads from the *previous* row (dp[i-1][w - weight_i]). If you collapse to a 1D array and iterate weight from low to high, you would read an already-updated value from the *current* row — effectively allowing item i to be used multiple times. By iterating from high to low, when you update dp[w], dp[w - weight_i] still holds the value from the previous row (before item i was processed), correctly enforcing the 0/1 constraint.
Question 4 True / False
Since the 0/1 knapsack DP runs in O(nW) time, it is a polynomial-time algorithm and can efficiently handle any input, including cases where W is a 100-digit number.
TTrue
FFalse
Answer: False
O(nW) is *pseudopolynomial* — polynomial in the numeric value of W, but not in the size of the input. The input size for W is O(log W) bits, so an algorithm polynomial in W is exponential in the number of bits needed to represent W. When W is a 100-digit number (roughly 10^100), the DP table is astronomically large and the algorithm is completely infeasible. The 0/1 knapsack problem is NP-hard; O(nW) does not contradict this because W itself can be exponentially large relative to input size.
Question 5 Short Answer
Why does the 0/1 knapsack problem require dynamic programming rather than a greedy approach, and what property of the problem makes greedy fail?
Think about your answer, then reveal below.
Model answer: Greedy fails because selecting items by value-to-weight ratio ignores how items interact with each other given the capacity constraint. The all-or-nothing rule means that choosing the highest-ratio item may consume capacity that would have been better used by a combination of smaller items. DP works because it exhaustively evaluates every possible subset by considering, for each item and each remaining capacity, whether to include or skip the item — capturing the interaction that greedy misses.
The greedy approach works for the *fractional* knapsack (where you can take parts of items) because the exchange argument holds: you can always swap a lower-ratio fraction for a higher-ratio one without loss. But in the 0/1 version, items are indivisible. This creates combinatorial dependencies among items that greedy cannot model. DP's recurrence makes these dependencies explicit: dp[i][w] considers both 'skip item i (inherited solution)' and 'take item i (adds its value, reduces capacity),' correctly modeling all interactions.