1. One-Liner
0/1 Knapsack builds a table dp[i][w]: the best value using the first i items with weight limit w, choosing each item once or not at all.
2. The Problem It Solves
Given weights w_i, values v_i, and capacity W, pick a subset with total weight ≤ W and maximum total value—each item can be taken 0 or 1 times (not fractional, not unlimited).
3. The Core Idea
For each item, either skip it (inherit best without it) or take it (add its value to the best at remaining capacity). The recurrence stitches smaller capacity and prefix decisions into the global optimum.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Init | dp[0][w]=0 for all w |
| 2. Items | For i from 1 to n, for w from 0 to W |
| 3. Skip | dp[i][w] = dp[i-1][w] |
| 4. Take | If w_i ≤ w, also consider v_i + dp[i-1][w-w_i] |
| 5. Result | dp[n][W] |
5. Dry Run Example
Items (w,v): (2,3), (1,2), W=3. Build row by row; best is 5 (take both).
6. Key Properties
| Property | Value |
|---|---|
| States | Prefix i, capacity w |
| Time | O(n·W) pseudo-polynomial |
| Space | O(W) with 1D rolling |
7. Where It Is Used
| Domain | Use |
|---|---|
| Resource allocation | Budget-limited project selection |
| Logistics | Loading with discrete choices |
8. Interview Tips
Discuss space optimization, subset reconstruction, and contrast with unbounded and fractional knapsack.
9. Comparison with Other Variants
| Variant | Items | Typical approach |
|---|---|---|
| 0/1 | At most once | 2D or 1D DP |
| Unbounded | Unlimited | Inner loop forward on w |
| Fractional | Split items | Greedy by value/weight |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n·W) |
| Space | O(n·W) or O(W) optimized |
Implementation Example (PYTHON)
def knapsack_01(weights, values, W: int) -> int:
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
w, v = weights[i], values[i]
for cap in range(W, w - 1, -1):
dp[cap] = max(dp[cap], v + dp[cap - w])
return dp[W]