What Is the Knapsack Problem?
The 0/1 Knapsack problem picks items, each with a weight and a value, to fit a weight-limited bag while maximizing total value. Each item is taken whole (1) or not at all (0) — it cannot be split.
With a take/leave choice per item, brute force explodes to 2ⁿ. Dynamic programming (DP) stores overlapping subproblems in a table and brings it down to O(nW).
Defining the State
dp[i][w] = the maximum value achievable considering the first i items with a weight limit of w.
This definition breaks the problem so that, seeing one more item, you only decide "do I take this item now?".
The Recurrence
If item i has weight wt and value v:
- •Leave it:
dp[i-1][w](same limit, same value) - •Take it (when w ≥ wt):
dp[i-1][w - wt] + v(subtract its weight from the limit, add its value) - •
dp[i][w] = max(leave, take)
It's all just choosing the higher-value of the two options.
How It Works
Step 1. Initialize dp[0][*] = 0 (no items → value 0).
Step 2. Add items one by one; for every weight limit w, fill the table with the recurrence above.
Step 3. dp[n][W] is the answer (max value with all items at the full limit).
1D optimization: keep a single row dp[w] and update w from high to low to shrink space to O(W).
The AlgoNote visualization fills the table cell by cell and shows which of "take/leave" gets chosen at each step.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(nW) |
| Space | O(nW) or O(W) |
n is the number of items, W is the weight limit.
Walking Through an Example
Items (weight, value) = (1, 6), (2, 10), (3, 12), limit W=5.
- •item 1 only: value 6 at limit 5
- •items 1·2: take both (1,6)+(2,10) → weight 3, value 16
- •items 1·2·3: (2,10)+(3,12) → weight 5, value 22 → max 22
dp[3][5] = 22 is the answer.
Common Mistakes
- •1D update direction: updating
dp[w]from low w lets you take the same item repeatedly (that's the "unbounded knapsack"). For 0/1 you must go high w first. - •Missing the limit check: only apply the take branch when
w ≥ wtto avoid negative indices. - •Huge W: if O(nW) is too costly, consider a value-indexed DP or another formulation.
See It in Action on AlgoNote
Watch the table fill as "take" and "leave" values are compared at each item, step by step on AlgoNote.