The Knapsack Problem
Best value that fits.
A hiker's bag can hold ten kilos. There are items of different weights and values, a tent, a camera, food, a book. Which items should she pack, to carry the most value without going over the limit? Each item is either packed, or left behind.

- A bag that holds 10 kg
- Items with weights and values
- Pack or leave each one
Zero one knapsack
Best of W means the best value we can carry with capacity W. For each item, we go through the capacities from high to low. Packing the item gives its value, plus the best value for the space that's left. We keep whichever is bigger, packing or not. Going from high to low makes sure each item is used only once. Run it. The best load is worth ninety five. The tent, the camera, and the stove, exactly ten kilos.
def knapsack(items, capacity):
best = [0] * (capacity + 1)
for name, weight, value in items:
for w in range(capacity, weight - 1, -1):
best[w] = max(best[w], best[w - weight] + value)
return best[capacity]
items = [("tent", 5, 40), ("camera", 2, 30), ("food", 4, 20), ("book", 3, 10), ("stove", 3, 25)]
print("best value:", knapsack(items, 10))best value: 95
Where knapsack appears
Knapsack is everywhere, in disguise. Choosing projects within a budget. Filling a delivery van. Picking adverts to fit a time slot. Whenever you choose items under a limit, to maximise a total, think knapsack. It runs in O of the number of items times the capacity.
| key | value |
|---|---|
| Budget | choose projects |
| Van | fill by weight |
| Adverts | fit a time slot |
| Cost | O(items × capacity) |
Summary
Zero one knapsack decides, for each item, whether packing it beats leaving it, for every capacity. Next, a dynamic programming puzzle about a careful burglar.
Key takeaways- best[w]
- Pack it or not
- Loop capacity downwards