0/1 Knapsack
Why it exists
Problem: You have a bag with a weight capacity and items with value and weight. You want to maximize value without exceeding capacity. Fractional knapsack can use greedy, but if you must take items whole (0/1), greedy fails.
Better idea: Use a 2D grid to track choices. At each item, compare the best value we can get if we include it (and deduct its weight from capacity) versus if we exclude it.
Mental model
For each item and every possible capacity, pick the winner: the item's value plus the best we could do with the remaining capacity, OR the best we did without this item.
Let `dp[i][w]` be the maximum value achievable using the first `i` items with exactly capacity `w`. The recurrence is `dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])`. If the item is heavier than `w`, `dp[i][w] = dp[i-1][w]`. The row index `i-1` in the include-branch is critical: it enforces that an item can be used at most once.
Repeated decision: For this item, does taking it (its value + the best answer for the remaining capacity, EXCLUDING this item from future consideration) beat leaving it out?
Explanation
This is the classic 2D 'choice + constraint' DP problem.
Let `dp[i][w]` mean: the best value using the first `i` items with a knapsack of capacity `w` -- that is, using total weight AT MOST `w`, not exactly `w`. The recurrence is:
- `dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])` when `weight[i] <= w`
- `dp[i][w] = dp[i-1][w]` otherwise.
Let's trace 3 items: Item 1 `(w=1, v=1)`, Item 2 `(w=3, v=4)`, Item 3 `(w=4, v=5)` with `W=6`. We fill row by row, where `dp[0][*]` is 0.
- **Row 1 (w=1, v=1):** Fits everywhere `w >= 1`. So `dp[1][1..6] = 1`.
- **Row 2 (w=3, v=4):** For `w=1..2`, it doesn't fit, so we copy above: `dp[2][1]=1`, `dp[2][2]=1`. For `w=3`, we take `max(skip:1, take:4+dp[1][0]) = 4`. For `w=4`, we take `max(skip:1, take:4+dp[1][1]) = 5`. It stays 5 for `w=5,6`.
- **Row 3 (w=4, v=5):** For `w=4`, `max(skip:dp[2][4], take:5+dp[2][0]) = max(5, 5) = 5`. For `w=5`, `max(skip:dp[2][5], take:5+dp[2][1]) = max(5, 5+1) = 6`. For `w=6`, `max(skip:dp[2][6], take:5+dp[2][2]) = max(5, 5+1) = 6`.
Note a crucial contrast: Fractional Knapsack allows taking parts of an item, so a simple greedy approach (highest value-to-weight ratio first) works perfectly. But here in 0/1 Knapsack where items are indivisible, greedy fails, which is why we must systematically check these combinations using DP.
Because `dp[i][w]` only ever looks up at the previous row `i-1`, we never take the same item multiple times. This allows us to space-optimize to a 1D array by iterating capacities right-to-left.
Key points
- Complexity: O(n*W) time and space, where `W` is the capacity. Space can be optimized to O(W) using a rolling array.
- The 0/1 Constraint: Using `dp[i-1][...]` instead of `dp[i][...]` ensures items are not reused. This distinguishes it from unbounded knapsack.
Common mistakes
- Iterating left-to-right in space optimization: When collapsing the 2D grid to a 1D array, scanning capacity left-to-right means `dp[w - weight[i]]` might have already been updated with item `i`. Scanning right-to-left ensures we only read values from the 'previous row' state.
- Confusing 0/1 with unbounded knapsack: If the recurrence was `dp[i][w] = max(dp[i-1][w], value[i] + dp[i][w - weight[i]])`, you would be allowed to reuse items (Unbounded Knapsack).
Recall questions
- What does `dp[i][w]` represent in the 2D Knapsack problem?
- What is the recurrence relation for 0/1 Knapsack?
- Why must you scan right-to-left when space-optimizing 0/1 Knapsack to a 1D array?
Questions & answers
Given an array of positive integers, can you partition it into two subsets with equal sums?
Yes, this is 0/1 Knapsack where the target capacity `w` is exactly half the total sum of the array, and the weights/values are the numbers themselves.
Approach: Recognize that 'finding a subset that sums to X' is a specialized case of Knapsack.
What if you can use each item an unlimited number of times?
This is Unbounded Knapsack. You simply change the transition to look at the current row: `value[i] + dp[i][w - weight[i]]`.
Approach: Identify the mechanism that enforces the constraint (the row index) and modify it to allow reuse.
Continue learning
Previous: Coin change
Next: Longest common subsequence
Next: Edit distance