← Lessons

quiz vs the machine

Gold1380

Algorithms

The Zero One Knapsack

Pick a subset of items under a weight limit to maximize value when each item is taken at most once.

5 min read · core · beat Gold to climb

The choice per item

You have items with weights and values and a capacity. Each item is either taken or left, never split or repeated. The state is dp at i and w, the best value using the first i items within capacity w.

The recurrence

For each item you decide to skip or take:

  • Skip it, giving dp at i minus one and w.
  • Take it if it fits, giving its value plus dp at i minus one and w minus its weight.

Take the larger of the two. The answer is the entry for all items at the full capacity.

Why the previous row matters

Because each item is used at most once, the take branch reads from the row that excludes the current item, that is i minus one. Reading the current row would allow reusing the same item, which belongs to a different problem.

Space note

Iterating capacity from high to low lets you collapse the table to a single row while still reading old values, because each item is consumed once.

Key idea

Zero one knapsack tries skip versus take for each item, always reading the previous item row so no item is reused, and keeps the better value at every capacity.

Check yourself

Answer to earn rating on the learn ladder.

1. Why does the take branch read from row i minus one?

2. What two options are compared for each item?

3. How can the table be reduced to one row?