0/1 Knapsack — 2D DP Table
Each item is either taken (1) or not (0). Fill a 2D table row-by-row.
Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
LC 416 (Partition Equal Subset Sum), LC 494 (Target Sum), LC 1049.
State:
Choice at each item:
dp[i][w] = max value using items 0…i with capacity w.Choice at each item:
- Skip item i:
dp[i-1][w]— same capacity, one fewer item. - Take item i (if w ≥ wt[i]):
dp[i-1][w-wt[i]] + val[i]— use remaining capacity and add value.
dp[i-1], never the same row.
Filled cell
Current cell
Source cells
Optimal path
Controls
Time: O(n·W) | Space: O(n·W)
Steps
0 stepsPress Run to trace the algorithm one step at a time.