0/1 knapsack
mediumLeaving an item inherits the row above; taking it looks back at reduced capacity and adds the value. The arrows show which, and following them back recovers the bag's contents.
O(n × W)Space O(n × W), or O(W) with the 1-D trickSaved in this browser - no sign-up, nothing sent anywhere.
How 0/1 knapsack works
dp[i][w] answers: using only the first i items, with capacity w, what is the best total value? Each cell faces one binary decision. Skip item i and the answer is dp[i-1][w], inherited from the row above unchanged. Take it - if its weight fits - and the answer is dp[i-1][w - weight] plus its value: the best result over the remaining capacity, from before this item existed.
Brute force tries all 2^n subsets - over a million for 20 items, over a billion for 30. Most of those subsets pass through identical states: same items considered, same capacity left. The table has only (n + 1) × (W + 1) such states, each resolved by one max of two numbers, so 30 items at capacity 100 costs about 3,000 cell fills instead of a billion subset checks.
Greedy by value density fails here because items are indivisible: a dense item can occupy capacity that two lighter items would have used better. The table cannot be fooled - both branches are evaluated at every capacity. And the answer is more than a number: recording which branch won at each cell lets a traceback from dp[n][W] name the exact items in the bag.
Step by step
- Three items - value 60 weight 1, value 100 weight 2, value 120 weight 3 - and capacity 5. Row 0 is all zeros: no items, no value.
- Row 1: item 1 fits everywhere from capacity 1 upward, so the row reads 0, then 60 all the way across.
- Row 2 at capacity 3: taking item 2 leaves capacity 1, worth 60, plus 100 makes 160 - better than the 60 from skipping.
- Row 2 settles at 0, 60, 100, 160, 160, 160 - item 2 alone beats item 1 alone at capacity 2.
- Row 3 at capacity 5: taking item 3 leaves capacity 2, worth 100, plus 120 makes 220. Skipping keeps 160. Take it.
- The corner dp[3][5] = 220. Traceback: 220 differs from the 160 above, so item 3 was taken - move to capacity 2.
- At dp[2][2], 100 differs from the 60 above - item 2 was taken, and capacity drops to 0. Items 2 and 3: weight exactly 5, value 220.
Complexity
| Worst case time | O(n × W) |
|---|---|
| Space | O(n × W), or O(W) with the 1-D trick |
The 1-D version needs a reversed inner loop, or it becomes unbounded knapsack.
Reference implementation
Python
def knapsack(values, weights, capacity):
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # skip item i
if weights[i - 1] <= w: # or take it
dp[i][w] = max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1])
return dp[n][capacity]
def knapsack_1d(values, weights, capacity):
"""Same answer in O(W) memory - note the REVERSED inner loop,
which stops an item being used twice."""
dp = [0] * (capacity + 1)
for v, wt in zip(values, weights):
for w in range(capacity, wt - 1, -1):
dp[w] = max(dp[w], dp[w - wt] + v)
return dp[capacity]JavaScript
function knapsack(values, weights, capacity) {
const n = values.length;
const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w]; // skip
if (weights[i - 1] <= w) { // take
dp[i][w] = Math.max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][capacity];
}Worth noticing
Two choices per item - that is the whole recurrence
Take it or leave it. Leaving it inherits the row above unchanged; taking it looks back to the row above at reduced capacity and adds the value. Every cell is one max of two numbers.
The arrows show where each answer came from
A straight-up arrow means the item was skipped; a diagonal one means it was taken. Following those arrows back from the corner reconstructs which items are in the optimal bag.
Why greedy by density fails here
Without fractions, a dense item can waste capacity that two lighter items would have filled better. The table tries both branches at every capacity, so it cannot be fooled - see the fractional knapsack for the case where greedy is right.
The 1-D optimisation, and its trap
Only the previous row is ever read, so one array suffices. But the inner loop must run *backwards*: forwards, dp[w − weight] would already hold this item's own contribution, and you would silently solve the unbounded knapsack instead.
Common pitfalls
- Running the 1-D inner loop forwards. dp[w - weight] then already contains this item's contribution, each item gets reused, and you have silently solved the unbounded knapsack.
- Skipping the copy when the item does not fit. dp[i][w] must still inherit dp[i-1][w], or every cell narrower than the item's weight reads zero.
- Off-by-one between table and arrays: row i describes item i, which lives at values[i-1] and weights[i-1].
- Trusting greedy by value-to-weight ratio. It solves the fractional knapsack, not this one - indivisible items make density misleading.
- Space-optimising to one row and then wanting the traceback. The 1-D version keeps the best value but discards which items produced it.
Where it is used
- Capital budgeting: choosing projects under a fixed budget to maximise total return.
- Cargo loading and cutting stock, where items cannot be split or partially taken.
- Subset sum and partition-equal-subset problems, which are knapsack with value equal to weight.
- A fixture of interview rounds - the canonical take-or-skip DP that most 2-D table problems are variations of.
Frequently asked questions
What is the time and space complexity of 0/1 knapsack?
Time is O(n × W) for n items and capacity W - one constant-time max per cell. Space is O(n × W) for the full table, or O(W) with the 1-D trick, at the cost of the traceback. W is the numeric capacity, so the cost is pseudo-polynomial.
Why must the 1-D knapsack loop run backwards?
The single array stands in for the previous row. Sweeping capacities from high to low, dp[w - weight] has not been touched this round, so it still holds the without-this-item value. Sweep forwards and it holds the with-this-item value - counting the item twice, which is the unbounded knapsack.
Isn't knapsack NP-hard? How can a table solve it?
The table is polynomial in the value of W, not in the size of the input - W takes only log W bits to write down. That is pseudo-polynomial time: practical for capacities in the thousands, useless when the capacity is astronomically large. The hardness and the DP coexist.
What is the difference between 0/1, fractional and unbounded knapsack?
0/1 takes each item whole or not at all, and needs this DP. Fractional allows splitting items, and a greedy sort by density is provably optimal. Unbounded allows unlimited copies of each item - same table, but the 1-D loop runs forwards instead of backwards.