The knapsack problem

An overnight hike into the mountains above Almaty. The tent, sleeping bag, food and water are already in the pack, and five kilograms are left for everything else. You would like to take sixteen things, from a down jacket and a stove to a book and a folding chair, and together they weigh 8.5 kg. You give each thing points for usefulness. Which set is best? There are 2¹⁶ = 65,536 sets, and each new thing doubles them. The table below finds the answer by filling 867 cells, and then tells you itself what to pack.

A row of the table is how many of the first things may be taken, a column how much room there is. A cell holds the best usefulness that can be carried under those conditions. The last cell, bottom right, is the answer: 64 points in exactly five kilograms. The green line is the path back, along which the table recovers the set itself from the bottom up: where the line, going up, shifts left, the thing is taken.

Beside it is the score of the simple rule “the most useful per gram first”. It collects 59 points: the pack fills with light bits and pieces, socks, a torch, cream, and when the turn comes to the stove with its pot there is no room left for 1.2 kg, and 700 grams stay empty. Change the points of the things, move the room, and see when greed guesses right and when not.

The idea

Look at the last thing. Either it is not in the best set, and then this is the best set of the other things with the same room. Or it is, and then the best set of the other things in the room left after it is added to its usefulness. Both subproblems are the same knapsack problem, only with one thing fewer. Solve them for all capacities at once and put them in a table.

Formally: the things are numbered, the i-th has weight w_i and usefulness p_i. best(i, c) is the largest usefulness of a set of the first i things weighing at most c. Then

and the second option exists only if w_i ≤ c. This problem, where each thing can be taken once or not at all, is called the 0-1 knapsack: each thing has only two decisions, zero or one. The rows of the table are computed from top to bottom, each only from the previous one, so the order of filling is obvious. This is the same dynamic programming as in any subproblem task: the state is the pair “how many things considered, how much room”, the transition is take or do not take.

Why the table is never wrong

The second paragraph uses what is called optimal substructure: if one thing is taken out of the best pack, what remains is the best pack for the smaller room. Otherwise the best pack could be improved by replacing the remainder with the best one.

What exactly to take

The table stores only numbers, but the set is recovered from it without trying anything. Stand in the last cell (n, W) and compare it with the cell above. If the numbers are equal, the best result can be achieved without thing n: go up a row. If they differ, so much cannot be collected without thing n, so it is taken: go up a row and shift left by its weight. After n steps the set is ready. This is the green line in the scene.

There can be several best sets, and the path back chooses one of them: on a tie it prefers not to take the thing. To recover the set you need the whole table, n + 1 rows of W + 1 numbers. If only the answer is needed, one row is enough, but more on that below: there is a trap.

Why not greedily

The greedy rule “the most useful per gram first” looks sensible and is sometimes even exact. If things can be cut, pouring half a kilogram of buckwheat from a bag, it really does give the best result: each gram of room goes to the most valuable thing still left. But the 0-1 knapsack cuts only by whole things, and room can be left unused. Look at the whole picture at once: for each capacity from zero to nine kilograms, the best pack and the greedy one.

The solid stepped line is the last row of the table, computed once up to nine kilograms: one row answers for all capacities at once. The dashed line is greed, which had to be run anew for each. It loses on 34 capacities of 90, by up to five points. The clearest case is half a kilogram: greed takes the torch, socks and cream, 300 grams and 12 points, and cannot take the rain jacket worth 8 points, because after the bits and pieces it is 100 grams short. The table packs the rain jacket, the torch and the socks, exactly 500 grams, 17 points.

It can be worse. Two things: the first weighs 1 gram and gives 2 points, the second weighs exactly the whole capacity of W grams and gives W points. By usefulness per gram the first is better, greed takes it, and the second no longer fits: 2 points against W. The error can be any number of times. Greed has a simple safeguard.

Code

The same hike: the table, the path back, the greedy rule and the last row, which answers for any capacity up to five kilograms.

Each row of the table depends only on the previous one, so the whole table can be replaced with one row updated in place. But the order of going through the row decides everything:

Right to left, cell c − w still holds the value from the previous row, that is, the best set without the current thing, and the thing is packed at most once. Left to right, cell c − w has already been updated in this row and may itself contain the current thing, and the program happily packs 50 head torches. The code differs in the direction of one loop and solves a different problem.

The unbounded knapsack

That very “mistake” becomes the right algorithm if there are as many things of each kind as you like: cutting a roll of cloth into pieces of standard lengths, making a sum from coins, loading a wagon with identical boxes of different types. The transition then looks at the same row:

and the loop over the room goes from left to right. The fewest coins for a sum from the introductory article on dynamic programming is the same unbounded knapsack, only instead of the most usefulness one looks for the fewest coins. In the third problem below, a cable roll up to 10¹² metres long: a table by metres will not fit into any memory, and you will have to notice that almost the whole roll goes on one and the same piece.

What it costs

There are (n + 1)(W + 1) cells, one comparison each: O(n·W) time. Memory is O(W) if only the answer is needed, and O(n·W) if the set is needed. The benchmark confirms it: with a fixed number of things the time grows in direct proportion to the capacity, and four times as many things take four times as long.

It looks like a polynomial, but that is a deception. W is not an amount of data but a number, and it is written with log₁₀ W digits. Append three zeros to the capacity, that is, take weight in grams instead of kilograms, and the input becomes three characters longer while the table becomes a thousand times wider. Time that is polynomial in the size of the numbers but exponential in the length of their notation is called pseudo-polynomial. Here are the same things weighed to the gram, as on the labels, and four units of weight:

With a column of a kilogram, each thing, even 85-gram socks, takes a whole kilogram, and five things fit into five columns: 35 points. With 100 grams the weight of each thing is rounded up, and the table finds 62 points, less than the 64 of the first scene, where the weights are rounded to the nearest hundred grams. With a unit of 10 grams the answer is exact, 64 points, but there are not 102 cells but 8517. Each further digit of precision multiplies the table by about ten, and with a unit of a gram it no longer adds anything to the answer.

Nobody can do faster: the subset sum problem, a knapsack where a thing’s usefulness equals its weight, was among Richard Karp’s 21 NP-complete problems in 1972. An algorithm polynomial in the length of the numbers’ notation would mean that P = NP (on this question, see the course chapter). So the weapon for the knapsack is chosen by the input:

• Few things, large weights. Up to forty things, meet in the middle helps: 2²⁰ sets for each half instead of 2⁴⁰.
• Large weights, small values. The table can be turned round: for each sum of values keep the smallest weight with which it can be collected. The size then depends on the sum of values, not on W. This is the second problem below.
• Approximation. Round the values to multiples of a suitable number, and a table by values becomes small. In 1975 Oscar Ibarra and Chul Kim showed that this gives an answer no worse than (1 − ε) of the best in time polynomial in both n and 1/ε.
• Pruning. Branch and bound tries sets but throws out branches whose fractional upper bound, that very greed with a piece, is worse than one already found.

Where it occurs

Wherever there is a budget and many ways to spend it: cutting sheets and rolls with the least waste, choosing projects and investments with limited money, loading transport. In 1999 Steven Skiena studied what visitors to Skiena’s algorithm repository looked for: among 75 problems the knapsack was nineteenth in popularity and third among those whose solutions were most needed, after suffix trees and bin packing. Often the knapsack hides inside another problem: which exam questions to spend limited time on if they are worth different marks, which adverts to put into a one-minute slot.

The knapsack cipher

Mathematicians were taking problems of this kind apart as early as the 19th century: George Mathews’s 1897 paper “On the partition of numbers” is considered one of the first. In 1956 Richard Bellman and Stuart Dreyfus at the RAND Corporation solved with dynamic programming the “cargo-loading problem”, where indivisible items created the difficulty, the same knapsack. In 1957 George Dantzig described the greedy way, taking in decreasing order of value per unit of weight, and the upper bound given by the fractional version; branch and bound methods still use it.

The most dramatic page of the history is cryptography. In 1978 Ralph Merkle and Martin Hellman published one of the first public-key encryption systems, built on subset sum. The secret is a superincreasing sequence, where each number is greater than the sum of all the previous ones. For it the sum problem is solved greedily: take the largest number not exceeding the remainder, and that is the only right choice. Merkle and Hellman disguised such a sequence by multiplication modulo a number, published the disguised numbers as the key, and encrypted a message as the sum of the numbers corresponding to its one bits. The calculation was that without the disguise the adversary gets the general subset sum problem with huge numbers, where the table from this article is hopeless.

But in 1982 Adi Shamir showed that the disguise gives itself away: from a single public key one can find in polynomial time numbers that turn it back into a superincreasing sequence. The knapsack problem stayed hard in general, but its special case with “disguised easiness” turned out easy. The lesson: it is not enough for a cipher that the problem be hard in the worst case; the instances that arise in encryption must be hard.

Problems

The first is a 0-1 knapsack with recovery of the set: a courier chooses orders. In the second the budget in tenge is so large that the table has to be turned round. In the third a cable roll up to a trillion metres long, and an idea will be needed, not a table.