The Problem
You have a backpack that can carry at most W kilograms, and n items each with a weight and a value. You want to fill the pack to maximise total value without exceeding the weight limit. Critically, each item is either fully taken or fully left — you cannot take a fraction of an item. That restriction is the "0/1" in the name.
Brute force: try every subset of items. With n items there are 2ⁿ subsets — exponential, and hopeless for large inputs.
The DP observation: the value you can achieve depends only on which items you have considered so far and how much capacity remains. Those two quantities define a subproblem.
Defining the Subproblem
Let dp[i][w] = the maximum total value achievable using only the first i items with a weight budget of exactly w.
Base case: dp[0][w] = 0 for all w — no items means zero value.
Transition: for item i (1-indexed, so it has weight weights[i-1] and value values[i-1]):
- Leave item i:
dp[i][w] = dp[i-1][w]— the best we could do with the firsti-1items. - Take item i: only possible if
weights[i-1] <= w. Value =values[i-1] + dp[i-1][w - weights[i-1]].
We take the maximum of the two options.
Answer: dp[n][capacity].
Code
Walking Through an Example
Items: weights = [2, 3, 4], values = [3, 4, 5], capacity = 5.
| i \ w | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 (none) | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 (w=2,v=3) | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 (w=3,v=4) | 0 | 0 | 3 | 4 | 4 | 7 |
| 3 (w=4,v=5) | 0 | 0 | 3 | 4 | 5 | 7 |
The answer is dp[3][5] = 7, achieved by taking item 1 (weight 2, value 3) and item 2 (weight 3, value 4). Item 3 (weight 4) would push over the budget once item 1 is taken.
Complexity
| Dimension | Cost | Why |
|---|---|---|
| Time | O(n · capacity) | Two nested loops, each linear in their dimension |
| Space | O(n · capacity) | Full dp table |
This is called pseudo-polynomial: it is polynomial in the numerical value of capacity, but that number could be exponentially large in the number of bits used to represent it. For small-to-moderate capacities the algorithm is fast in practice.
Space optimisation. Each row of the table only reads from the row above (i-1), so you can compress to a single 1D array by iterating w from right to left (to avoid using items more than once):
Interactive Lab
Watch the DP table fill row by row. Each cell shows the best value reachable with the items considered so far at that capacity.
Key Takeaways
- The core insight: define
dp[i][w]as "best value using first i items with capacity w", then write the take-or-leave recurrence. - The transition is clean and local: each cell depends only on the row above and the same row shifted left by the item's weight.
- Time is O(n · capacity) — fast when capacity is small, pseudo-polynomial in general.
- The 1D rolling optimisation halves memory and is the standard production form.
- The knapsack pattern generalises widely: subset-sum, partition-equal-subset, and target-sum problems all reduce to a variant of this table.