Knapsack

The problem

You have a bag that holds at most W kilograms and a pile of items, each with a weight and a value. Which items should go in so the total value is as high as possible without the bag going over its limit? Every item is all or nothing: you can't pack half a tent.

Swap kilograms for dollars and it becomes budget allocation: projects with costs and expected returns, a fixed budget. Swap them for cubic metres and it's cargo loading. Investment selection, ad-slot planning, choosing which features fit in a release: whenever you pick a subset under one capacity limit, it's a knapsack in disguise. It also turns up inside bigger solvers, for example in column generation for cutting-stock problems.

Formal model

Give each item i a decision variable x_i, which is 1 if the item is packed and 0 if not. The 0-1 knapsack problem is then:

That's an integer linear program with a single constraint. Drop the requirement that x_i be 0 or 1 and allow fractions, and the problem becomes easy: greedy by value per kilogram is then exactly optimal. The whole difficulty lives in that little ∈ {0, 1}.

Why it's hard

With n items there are 2ⁿ possible selections. 30 items give over a billion; 60 items give more than a billion billion. Checking them all is hopeless, and no known algorithm avoids exponential time in the worst case: the decision version ("can we reach value V?") is NP-complete, one of Richard Karp's 21 classic NP-complete problems from 1972.

And yet the dynamic program in this lab solves real instances quickly. The catch is in its running time, O(n·W): it depends on the value of the capacity, not on the number of digits needed to write it down. Add one digit to W and the table gets ten times wider. Algorithms like this are called pseudo-polynomial: fast when the numbers are small, exponential in the size of the input when they're huge. That's why knapsack is called "weakly" NP-hard.

Data structures

The DP table

The core of the exact method is a two-dimensional array dp[i][w] with n + 1 rows and W + 1 columns. Cell dp[i][w] answers a smaller question: what's the best value using only the first i items with capacity w? Each cell depends on just two cells in the row above, so the table fills row by row in a fixed order, with no recursion and no repeated work.

Keeping the whole table costs O(n·W) memory but lets you walk back from the bottom-right cell to recover which items were chosen: whenever a cell differs from the one above it, that row's item was packed. If you only need the best value, one row of length W + 1 is enough: sweep it from right to left for each item, and memory drops to O(W).

A sorted array for greedy

The greedy heuristic needs nothing more than the items sorted by value per kilogram. Sorting dominates its cost at O(n log n); the packing pass afterwards is a single loop.

The algorithms

Dynamic programming (exact)

The key observation is the principle of optimality: in the best packing for capacity w, either item i is left out, and the rest is the best packing of the first i − 1 items for w, or it's in, and the rest is the best packing of the first i − 1 items for w − w_i. Compare the two and keep the larger. Step through the lab and watch each cell make exactly that decision.

Branch and bound (exact)

Brute force walks a binary tree: each level decides one item, take it or skip it, and the 2ⁿ leaves are all possible packings. Branch and bound walks the same tree but carries two numbers. The best is the value of the best packing found so far. A node's bound is an optimistic estimate of anything below it: fill the remaining room greedily by density and allow one item to be taken fractionally. Because fractions make the problem easier, the bound can never be beaten. When a node's bound is no better than the best, its whole subtree is cut unexplored.

Two choices make the cuts happen early. Items are decided densest first, and "take" is tried before "skip", so a strong packing is found quickly and raises the bar for everything after it. Watch the node count in the lab: on most examples the search visits a small fraction of the full tree, yet the answer is proven optimal, just like dynamic programming. Unlike the DP, its running time doesn't depend on the size of W, which is why solvers prefer it for huge capacities.

As an integer program

The "Integer program" option solves the formal model above the way general-purpose solvers do. It drops the 0-or-1 rule, solves the resulting linear program with the simplex method, and branches on a variable that came out fractional: one child forces it to 1, the other to 0. For knapsack the relaxation is exactly the fractional greedy bound, but the search branches on the item that is split, not simply the next one in line, so it usually needs far fewer nodes than plain branch and bound. On the camping trip it proves the optimum after five linear programs.

Greedy by value density

Rank items by value ÷ weight and pack each one that still fits. It's intuitive and instant, but it can be badly wrong. In the greedy trap example, the statue has the best ratio, so greedy packs it first and then can't fit the painting and the vase, which together are worth more. Greedy can be made safe with one small fix: return the better of the greedy packing and the single most valuable item that fits. That simple variant is never worse than half the optimum.

Beyond this lab

• Approximation schemes. Round values down to a coarser scale and run a DP over values instead of weights. You choose the accuracy ε and pay for it in time: a fully polynomial-time approximation scheme (FPTAS).
• Meet in the middle. Split the items in half, list all subsets of each half, sort one list, and match. That's about 2^n/2 work instead of 2ⁿ, useful when weights are huge but n is around 40.
• Variants. Unbounded knapsack (unlimited copies of each item), bounded knapsack (up to k copies), multidimensional knapsack (weight and volume limits), multiple knapsacks, and quadratic knapsack, where pairs of items add value together.

A little history

The name is usually credited to the mathematician Tobias Dantzig in the early twentieth century. His son George Dantzig, the inventor of the simplex method, studied the problem in 1957 and gave the greedy ratio rule and the LP-relaxation bound still used in branch and bound today. Dynamic programming came from Richard Bellman in the 1950s. Karp's 1972 paper put knapsack on the first list of NP-complete problems, and in 1975 Ibarra and Kim showed it could be approximated as closely as you like in polynomial time.

The problem even had a turn in cryptography: the Merkle–Hellman cryptosystem of 1978 hid messages in knapsack instances. Adi Shamir broke it in 1982, a reminder that "NP-hard in the worst case" doesn't mean every instance is hard.