0/1 Knapsack & Dynamic Programming

A packing problem with no shortcuts

You have a knapsack with capacity W, and n items, each with a weight and a value. You may take each item whole or not at all — no cutting an item in half, hence "0/1". The goal is to choose the subset of items that maximises total value while keeping total weight at or under W. With n items there are 2^n possible subsets, and checking them all is only feasible for tiny n. Dynamic programming turns this exponential search into something far cheaper by noticing that the problem has overlapping subproblems.

The take-vs-skip recurrence

Define dp[i][w] as the best value achievable using only the first i items with a capacity budget of w. For item i, there are exactly two choices, and dp[i][w] is the better of them:

dp[0][w] = 0                                    for all w   (no items yet)

dp[i][w] = dp[i-1][w]                            if weight[i] > w   (must skip — too heavy)

dp[i][w] = max( dp[i-1][w],                      // skip item i
                dp[i-1][w - weight[i]] + value[i] )  // take item i
                                                  otherwise

Every cell only needs the row directly above it, so the whole table can be filled row by row, left to right, in O(n·W) time and, if you only need the final value, O(W) space by keeping a single rolling row (iterated from high w down to low w, so each item is only used once). The very last cell, dp[n][W], is the answer.

live demo · the DP table filling in, cell by cell● LIVE

Backtracking to recover the actual items

The table gives you the optimal value, but usually you also want to know which items to pack. Starting at dp[n][W], compare it to dp[n-1][W]: if they are equal, item n was not needed, so move to dp[n-1][W] and repeat; if they differ, item n must have been taken, so record it and move to dp[n-1][W - weight[n]]. Repeating this all the way back to dp[0][0] reconstructs exactly one optimal item set, in O(n) extra steps once the table is built.

Why greedy fails here

A natural shortcut is to sort items by value-to-weight ratio and greedily take the best ratio first, as long as it still fits. This is provably optimal for the fractional knapsack, where items can be split — but for 0/1 knapsack it can be arbitrarily bad. A single example makes it obvious: with capacity 10 and two items, one weighing 6 worth 6 (ratio 1.0) and one weighing 5 worth 5.5 and another weighing 5 worth 5.5 (ratio 1.1 each), greedy grabs the item with the marginally worse ratio... the underlying issue is always the same: greedy commits early to whichever item looks best in isolation and can leave capacity stranded that a different combination would have used completely, whereas the DP recurrence correctly compares every combination implicitly through its two-choice recursion.

When the table itself becomes the bottleneck

The O(n·W) running time is deceptive: it looks polynomial in the input size, but W is a number, and the input only needs about log₂(W) bits to encode it — the algorithm is pseudo-polynomial. For a capacity of a few thousand this is instant; for a capacity in the billions the table becomes impossibly large even though n itself is small. Real logistics and finance applications with huge capacities or continuous weights instead turn to branch-and-bound, meet-in-the-middle for moderate n, or approximation schemes that trade a small, provably bounded loss of optimality for tractable running time.

Frequently asked questions

Why does the greedy approach — always take the best value-to-weight item first — fail on 0/1 knapsack?

Because you cannot take a fraction of an item. Greedy can fill the capacity with a high-ratio item that leaves an awkward amount of room left over, wasting space that a different, slightly lower-ratio combination would have used completely. It works for the fractional knapsack variant, where items can be split, but not for 0/1.

Is the dynamic programming solution to 0/1 knapsack fast in a rigorous sense?

It runs in O(n·W) time, which looks polynomial but is not, because W is a number, not the size of the input — the input only needs log(W) bits to write down. This is called pseudo-polynomial time, and it is why the DP table becomes impractically large when capacities are in the millions, even though it is entirely tractable for the small capacities typical in a teaching example.

What changes if you can take multiple copies of the same item?

That is the unbounded knapsack problem, and it only needs a one-line change to the recurrence: when considering an item you allow yourself to reuse the current row instead of only the row above, since taking one copy does not forbid taking another. The 0/1 constraint disappears and the DP still runs in similar pseudo-polynomial time.

Try it live

Everything above runs in your browser — open 0/1 Knapsack and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open 0/1 Knapsack simulation

0/1 Knapsack: Dynamic Programming, Cell by Cell