0/1 Knapsack

0/1 Knapsack is a dynamic programming algorithm for choosing items under a fixed capacity limit. Each item can be taken once or skipped, so the table records the best value for every prefix of the item list and every possible capacity. The animated version runs in O(n * capacity) time.

Think of the table as a notebook with one strict rule: when you decide whether to use item i, you may only read the row above it. That row means "before this item existed." The rule is small, but it blocks the classic mistake of accidentally packing the same item twice. It is the same shape as a budget decision: spend each grant, hour, or truck slot at most once.

How 0/1 Knapsack Works

The state is dp[i][w]: the best value you can get using only the first i items with capacity w. Row 0 is all zeroes because no items means no value. Column 0 is all zeroes because a bag with no capacity cannot hold anything.

For every real item row, the algorithm tries capacities from left to right. If the item is too heavy for the current capacity, there is no choice: copy the value from the row above. That is the skip branch.

If the item fits, there are two candidates. skip is still dp[i - 1][w], the best answer without the item. take is the item's value plus dp[i - 1][w - weight], the best value you could already make with the remaining capacity. The cell gets the larger number.

The important part is not the max. The important part is where the two reads come from: both are in row i - 1. A 0/1 item never reads from its own row, so it never helps pay for itself twice. That is the difference between 0/1 knapsack and unbounded knapsack.

After the table is full, the algorithm traces backward from dp[n][capacity]. If dp[i][w] equals the cell above, item i was skipped. If it differs, item i was taken, and the traceback moves diagonally to w - weight.

0/1 Knapsack Step by Step

The default run uses capacity 9 and five items:

First the base row and base column become zero. This is not decoration; every later candidate eventually bottoms out there.

Item A weighs 2. At capacity 1 it is too heavy, so the table copies 0 from above. At capacity 2, the first take beat reads dp[0][0], not dp[1][0]; that is the 0/1 rule in miniature. From there onward, taking A gives value 3, so row A becomes 0, 0, 3, 3, 3, 3, 3, 3, 3, 3.

Item B weighs 3. Capacities 1 and 2 copy the old row. At capacity 3, B beats A alone with value 4. At capacity 5, the diagonal read reaches dp[1][2] = 3, so taking B plus A gives 4 + 3 = 7. From there through capacity 9, the best value is 7.

Item C weighs 4 and is worth 8, so it changes the table fast. At capacity 4, taking C gives 8. At capacity 6, C plus A gives 11. At capacity 7, C plus B gives 12. At capacity 9, C plus the best capacity-5 answer from the row above gives 15.

Item D also has value 8, but it weighs 5. Some cells keep the old answer: at capacity 6, skip = 11 and take = 8, so skipping wins. At capacity 8, both candidates give 12; the animation records the tie as a skip so the later traceback is deterministic. At capacity 9, D finally wins: 8 + dp[3][4] = 8 + 8 = 16.

Item E has the largest single value, 10, and that is exactly why it is useful in the example. At capacity 8 it improves one cell to 13, but at capacity 9 it loses to the old 16. The table refuses the flashy item because C + D already fills the bag better.

The traceback starts at dp[5][9] = 16. E is skipped because the value equals the cell above. D is taken, so capacity drops from 9 to 4. C is taken, so capacity drops to 0. B and A are skipped. The chosen set is C + D, total weight 9, total value 16.

Time and Space Complexity

Edge Cases

• Capacity 0 returns value 0 and chooses no items.
• An item heavier than the current capacity must copy from the row above.
• If no item fits, the final answer stays 0.
• Exact fits are ordinary take candidates: if weight == w, the diagonal source is column 0.
• Ties need a deterministic rule. This animation keeps the skip candidate, so traceback does not flicker between equivalent answers.

Common Mistakes

• Reading from dp[i][w - weight] in 0/1 knapsack. That reuses the same item and turns the algorithm into unbounded knapsack.
• Sorting by absolute value and calling it done. The greedy-trap preset is exactly that bug: value greedy grabs A for 30, while DP finds B + C for 56. Do not relabel this preset as ratio greedy; B and C have the better ratios here.
• Forgetting the extra base row and base column. Without them, the first item and capacity-zero cases need special branches everywhere.
• Tracing forward through the table. The item set is recovered backward from the final cell, comparing each cell with the one above it.
• Mixing units. Weight and capacity are the same unit; value is a separate score. Adding two values is fine. Adding value to weight is nonsense with nicer handwriting.

A Note on Simplification

The animation shows the full 2-D table because the table explains the recurrence. Production code can compress the table to one row if it iterates capacities backward, but that optimization hides the previous-row rule that makes 0/1 knapsack work. This lesson teaches the full table first on purpose, on small integer weights and a handful of items — a real solver handles thousands of items with the same recurrence.