Skip to content
← Back to algorithms

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How this algorithm works

How it works

  1. Build a table with one row per item and one column per capacity from 0 up.
  2. Row 0 is the empty bag: nothing chosen, value 0 everywhere.
  3. For each cell, ask whether this item even fits in this capacity.
  4. If it does not fit, copy the answer from directly above — the item changes nothing.
  5. If it fits, compare skipping it against taking it plus the best use of the remaining capacity.
  6. Take the larger of the two. The bottom-right cell is the answer.

Key concepts

  • Each cell depends on exactly two cells in the row above
  • 0/1 means each item is taken whole or not at all
  • Pseudo-polynomial: the cost scales with the capacity number, not its digit count
  • The row above is all you need, so O(W) space is enough

When to use it

Resource allocation with indivisible choices and a hard limit — budgeting, cargo loading, cutting stock. If items can be split, a greedy ratio sort solves it faster.

Did you know

The 0/1 knapsack is NP-hard, yet this table solves it in nW steps — no contradiction, because W is a value, not an input size.