Overview
0/1 Knapsack: given items with weight and value, maximize total value without exceeding capacity.
Analogy
Packing for a trip: you can take each item at most once; maximize what you bring within weight limit.
Step-by-step
- dp[i][w] = max value using first i items and capacity w.
- For each item i: for w = 0..W. If w<weight[i]: dp[i][w]=dp[i-1][w]. Else: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]).
- Answer is dp[n][W].
Visual
Items [(2,3),(3,4),(4,5)] W=5 → dp table → max value=7 (items 0+1)
Common mistakes
- Using 1D array but iterating forward (must iterate w backwards for 0/1 knapsack).
- Forgetting to copy dp[i-1] row when using 1D optimization.
Practice questions
- Reconstruct which items were picked by backtracking the dp table.
- Solve subset sum (value=weight, target=W).
Space
O(W) with 1D optimization
AI Wisdom