Overview
The 0/1 Knapsack problem asks which subset of items, each with a weight and a value, fits inside a weight limit while maximising total value. The 0/1 in the name means each item is either taken whole or left behind — no fractions.
That restriction is what makes it hard. The fractional version yields to a greedy rule — sort by value per unit weight and fill — but greedy fails here, and it fails in a way worth seeing: a single heavy, high-value item can beat several light ones with better ratios. Every cell of the DP table answers one question about one item: skip it, or take it and spend its weight?
How 0/1 Knapsack works
- Build a table where row i covers the first i items and column w covers a capacity budget from 0 up to W.
- Row 0 is all zeros: with no items available, no capacity yields any value.
- For each cell, first consider skipping item i — the answer is simply the cell directly above.
- If item i fits in the current capacity, also consider taking it: its value plus the best result for the remaining capacity from the previous row.
- Store the larger of the two. The final cell holds the maximum value; walk back up comparing each cell with the one above to recover which items were taken.
When to use it
- Budget allocation: picking the set of projects with the highest combined return under a fixed spend.
- Cargo and container loading, where items are indivisible and capacity is hard-limited.
- Resource scheduling under a CPU, memory or bandwidth cap, with each task an all-or-nothing choice.
- The template for a whole family: unbounded knapsack, subset sum, partition equal subset sum and coin change are all variations on this table.
Complexity analysis
Time and space are both O(n·W), where n is the item count and W the capacity. That looks polynomial but is not, in the strict sense: W is a numeric value, and writing it down takes only log W bits, so the table grows exponentially in the size of the input encoding. This is what 'pseudo-polynomial' means, and it is why 0/1 knapsack is NP-hard despite having a table-filling solution. Space can be reduced to O(W) with one row, iterating capacity downwards so each item is used at most once.
Frequently asked questions
Why does the greedy value-per-weight rule fail?
Because taking the best-ratio item can leave a remainder of capacity too small to be useful. With capacity 10 and items (6kg, $30) and two of (5kg, $20), the best ratio is the 6kg item at $5/kg — take it and 4kg is wasted, for $30. Taking both 5kg items gives $40. Greedy cannot see that trade because it never reconsiders.
Why does the one-row optimisation iterate capacity backwards?
Going forwards would read a cell already updated for the current item, which amounts to taking that item twice — that is exactly the unbounded knapsack. Iterating downwards guarantees every value you read still belongs to the previous row.
What if capacities or weights are not whole numbers?
The table is indexed by capacity, so it needs discrete steps. Scaling to a fixed precision — grams instead of kilograms — works but multiplies W and therefore the runtime. When precision is high, approximation schemes or branch and bound replace the table.