The knapsack problem
A hiker with a weight limit, a thief with a sack, a company with a budget and a list of projects: all face the same question. Which things should go in to get the most value without going over the limit? It is the knapsack problem, and dynamic programming solves it exactly when the weights are whole numbers of moderate size.
The problem
There are n items, each with a weight and a value, and a bag that holds at most a weight W. Choose a set of items whose total weight is at most W and whose total value is as large as possible. Every item goes in whole or stays out, which is why it is called the 0/1 knapsack problem. With n items there are 2ⁿ possible sets, so trying them all soon becomes impossible.
The table
Let best[i][w] be the most value that fits in weight w using only the first i items. Then best[0][w] = 0, and for each later row there are two choices: leave item i out, giving best[i − 1][w], or, if its weight wᵢ fits, pack it, giving its value plus best[i − 1][w − wᵢ]. The larger one is best[i][w]. Filling the table row by row means both cells it needs are always ready.
An example
Take a capacity of 7 and four items with weights 1, 3, 4 and 5 and values 1, 4, 5 and 7. With only the first item, every capacity from 1 up is worth 1. Adding the second, capacity 4 can hold both for 5. Adding the third, capacity 7 can hold items 2 and 3 for 9. The fourth item, weight 5 and value 7, could join item 1 for 8 at capacity 6 or 7, but 9 is better, so the bottom right cell is 9: pack the items of weight 3 and 4.
How hard is it?
The table needs about n·W steps. That looks fast, but W is a number, and a number with d digits can be as large as 10 to the power d, so the work grows exponentially with the length of the input. The knapsack problem is NP-hard; it was one of Richard Karp's 21 NP-complete problems of 1972. In practice the table, branch and bound, and good approximation schemes handle large real instances well.
History and uses
The name goes back to the mathematician Tobias Dantzig in the early 20th century, and his son George Dantzig gave a classic greedy method for it in 1957. Knapsack problems turn up in budgeting and portfolio selection, in cutting raw material with as little waste as possible, in loading cargo, and even in early public-key cryptography: the Merkle–Hellman cryptosystem of 1978 was built on a knapsack problem, and was broken a few years later.
Explore it
Open the app, switch to the Table view and press Step. The orange cell is being filled, and the blue cells are the two it compares: the cell directly above, and in the row above, the cell the item's weight to the left. After the last cell, the read-back climbs from the bottom right corner in orange, and the packed items appear under the table.
Frequently asked questions
What is the difference between 0/1, bounded and unbounded knapsack?
In the 0/1 version each item is taken at most once. In the bounded version each item has a limited number of copies, and in the unbounded version any number. The table changes only slightly between them.
Is the greedy method ever right for knapsack?
For the fractional knapsack problem, where items can be split, taking the best value per weight first is optimal. For whole items it can be far off, although the better of greedy and the single most valuable item is always at least half the best value.
How much memory does the table need?
(n + 1)·(W + 1) cells for the full table, which is what you need to read the items back. If only the best value is wanted, one row of W + 1 cells is enough, filled from right to left.
Is knapsack the same as subset sum?
Subset sum is the special case in which every item's value equals its weight and the question is whether the bag can be filled exactly. It is NP-complete as well and is solved by the same kind of table.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try the knapsack problem