A hiker has a rucksack that can hold at most 10 kilos and a pile of useful items, each with a weight and a usefulness. They cannot take them all. Which ones should they choose to maximise total usefulness without exceeding the limit? The knapsack problem looks like a game, but it describes countless real decisions: which projects to fund with a fixed budget, which files to put on a medium of limited capacity, which adverts to fit into an advertising slot, which loads to put on a lorry.
The 0/1 version
We have n items; item i weighs w_i and is worth v_i. The capacity is C. Each item is either taken whole or left: no fractions. We want to maximise the sum of values, with the sum of weights at most C.
Trying every subset requires 2^n attempts: with 40 items that is more than a thousand billion. The problem is NP-hard in general, but when weights and capacity are integers that are not too large, dynamic programming solves it exactly and quickly.
The recurrence
The state is a pair (i, c): the best value obtainable using only the first i items with capacity c. For item i there are two choices:
- leave it: the value stays that of (i − 1, c);
- take it, if w_i ≤ c: the value is v_i plus the best obtainable with the first i − 1 items and remaining capacity c − w_i.
Therefore:
M(i, c) = max( M(i − 1, c), v_i + M(i − 1, c − w_i) )
with M(0, c) = 0 for every c.
A complete example
Capacity 7. Items:
| Item | Weight | Value |
|---|---|---|
| Tent | 4 | 10 |
| Stove | 3 | 7 |
| Sleeping bag | 2 | 6 |
| Torch | 1 | 2 |
Several combinations respect the capacity: tent + stove (weight 7, value 17), tent + sleeping bag (weight 6, value 16), stove + sleeping bag + torch (weight 6, value 15), tent + sleeping bag + torch (weight 7, value 18). Filling the table row by row gives, in the last row and column 7, precisely the value 18.
To find out which items make up the optimum, walk back through the table: torch taken (remaining capacity 6), sleeping bag taken (remaining 4), stove not taken, tent taken (remaining 0). Note that tent + stove, the choice that fills the rucksack with the two most valuable items, is worth only 17.
This example also shows why reconstruction must be done carefully: compare M(i, c) with M(i − 1, c) and, if they differ, item i was taken.
The code with reduced memory
Each row of the table depends only on the previous one, so a single array of C + 1 elements is enough, provided capacities are scanned from largest to smallest:
def knapsack(weights, values, C):
M = [0] * (C + 1)
for w, v in zip(weights, values):
for c in range(C, w - 1, -1):
M[c] = max(M[c], v + M[c - w])
return M[C]
Scanning backwards guarantees that M[c − w] still refers to the previous row, that is, that the same item is not used twice. Scanning forwards would instead solve the unbounded knapsack, in which each item is available in unlimited quantity: a mistake that changes the problem without giving any sign.
The cost is proportional to n · C. Be careful: it is fast if C is small, but C is a number, not an amount of data. With capacities expressed in grams instead of kilos the table becomes a thousand times larger. This is why it is called a pseudo-polynomial algorithm.
The fractional knapsack
If items can be divided (sand, liquids, hours of work), the problem becomes easy. Sort the items by decreasing value per unit of weight and fill the rucksack in that order, taking a fraction of the last item that does not fit whole. This greedy approach is optimal for the fractional version, but not for the 0/1 one: in the example the highest ratio is the sleeping bag's (3 per kilo), followed by the tent (2.5), the stove (about 2.33) and the torch (2).
When the capacity is too large
If weights and capacity are huge numbers, the table is not practical. The alternatives:
- DP over values: if values are small, compute the minimum weight needed to achieve each possible value;
- branch and bound: use the fractional knapsack as an upper bound to prune the tree of choices; on many real instances it is very efficient;
- approximation schemes: by rounding values to multiples of a chosen unit you get a solution guaranteed to be within a chosen percentage of the optimum, in polynomial time;
- greedy heuristics: fast and often good, but without guarantees.
Common variants
- Multidimensional knapsack: several constraints at once, such as weight and volume, or budget and staff.
- Multiple knapsack: several containers, such as several lorries or several disks.
- Subset sum: the case where value and weight coincide; it asks whether exactly a given sum can be reached.
In short
- The 0/1 knapsack chooses a subset of items of maximum value within a capacity.
- Dynamic programming over (item, capacity) solves it in n · C time.
- With a single array, capacities must be scanned backwards, otherwise you solve the unbounded knapsack.
- The fractional version is solved by sorting on value per unit of weight.
- For huge capacities you need branch and bound, approximations or heuristics.
