Card 01/ 09
0/1 Knapsack: Choosing Items Under a Capacity
Each item is either skipped or taken once, and a table over items and capacities holds the best value for every pair.
The 0/1 knapsack problem picks items, each with a weight and a value, to get the most value without the weights passing a capacity, where every item is either left out or taken whole, once. This card gives the state and the recurrence that solve it with a table over items and capacities, the cues that say a problem is a knapsack, and why no greedy rule solves it.
A courier has a bag that holds 6 kilos and three parcels to choose from, each paying a fee on delivery. Parcels cannot be split. The run below lists them with the value each earns per kilo.
| Parcel | Weight, kilos | Value, pounds | Value per kilo |
|---|---|---|---|
| A | 2 | 3 | 1.50 |
| B | 3 | 5 | 1.67 |
| C | 4 | 6 | 1.50 |
Taking the best value per kilo first takes B, then A, for 5 kilos and £8, and C no longer fits. A and C together weigh exactly 6 and are worth £9. A run confirmed both figures. The greedy rule spent its first choice on B and left room that nothing else could fill; Greedy Algorithms showed the same failure with whole parcels in a van.
The dynamic programme keeps every option open with one state: best[i][c] is the most value from the first i items with capacity c. Item i is either skipped, which leaves best[i − 1][c], or taken, if its weight w fits, which leaves best[i − 1][c − w] plus its value v. So best[i][c] = max(best[i − 1][c], best[i − 1][c − w] + v), with best[0][c] = 0 because no items are worth nothing. The answer is best[n][W], for all n items and the full capacity W. Packing a suitcase this way means trying each item against every amount of room the case might have left, then keeping whichever choice was worth more; unlike a person packing by eye, the table tries every capacity, including ones no packing ever reaches.
- State
- best[i][c], the most value from the first i items with capacity c
- Recurrence
- max(skip: best[i − 1][c], take: best[i − 1][c − w] + v)
- take only when w ≤ c
- Time
- O(n × W)
- pseudo-polynomial, since W is a value
- Space
- O(n × W) for the table, O(W) for one array
- one array cannot recover the items
Three cues mark a problem as a 0/1 knapsack: each thing can be used at most once, there is a limit on a total such as a weight, a budget or a time, and the goal is to make another total as large or small as possible. Choosing talks for a conference day, projects within a budget, or files to fit on a disk all match. A problem where items may be cut, like loose goods in a van, is not a knapsack in this sense: there value per kilo is optimal and no table is needed.
The O(n × W) cost is fine when W is modest, such as kilos or pounds up to a few thousand, and too large when W is measured in fine units like grams or pence over big totals, as Costing a Dynamic Programme: States Times Work per State explains.
← → move through sections and cards