Advanced · Module 18 · Lesson 3
0/1 knapsack
Choose each item at most once.
Lesson 107 of 123
1d streak0/1 Knapsack: Bounded Choice & 1D Space Optimization
The 0/1 Knapsack problem considers N items with weights and values, and a maximum bag capacity W. Each item can either be taken once (1) or left behind (0). A 2D DP matrix dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) solves the problem in O(N * W) time. Iterating capacity backwards optimizes space to a single 1D array of size O(W).
public int knapsack(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
// Iterate backwards so each item is used at most ONCE
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}Active Recall Checkpoint
Why MUST the capacity loop iterate backwards (capacity down to weight) in 1D space optimization?
Show answer & explanation
Iterating forward (0 up to capacity) allows dp[w] to read a value updated earlier in the SAME item iteration, which models the Unbounded Knapsack (unlimited item reuse). Iterating backward guarantees values read from dp[w - weight] are strictly from the previous item.
Use it when
Use 0/1 Knapsack for subset sum partitioning, target sum, bounded budget allocation, and coin change with limited supplies.
Reconsider when
Reconsider when items can be chosen unlimited times (use Unbounded Knapsack with forward iteration) or when items can be split fractionally (use Greedy O(n log n)).
Cost Model
Complexity & Trade-offs
When to use it
- Optimization, counting, and feasibility with overlapping subproblems.
- Sequence, grid, interval, tree, subset, and digit constraints.
- Replacing exponential recursion with reusable state.
Common mistakes
- Defining a state that lacks information needed by the transition.
- Iterating in an order that reads unresolved or same-round values.
- Optimizing space before proving dependencies.
Practice prompts
- Reproduce the worked 0/1 knapsack example without looking at the trace.
- Change one input condition and explain whether the 0/1 knapsack invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check