The Knapsack Problem
A burglar stands in a vault with a sack that holds only so much weight. Around them sit gold bars,
jewels and cash — each item worth something, each weighing something. Grab too much and the sack
breaks; grab timidly and you leave a fortune behind. Which subset of loot maximises the value carried
out? That is the knapsack problem, and it is far more than a heist puzzle: it is the
skeleton of budgeting, cargo loading, capital rationing, cutting stock and CPU scheduling — anywhere you
must pick a subset of items to maximise value under a single capacity limit.
The 0/1 knapsack, precisely
You have n items. Item i has value
v_i and weight w_i, and the sack's capacity is
W. Each item is taken whole or left behind — you cannot take half a
gold bar — so the decision is a binary variable
x_i \in \{0,1\}. This makes knapsack a pure
binary integer program:
- Maximise the total value \displaystyle \sum_{i=1}^{n} v_i x_i;
- subject to the capacity \displaystyle \sum_{i=1}^{n} w_i x_i \le W;
- with each x_i \in \{0,1\} (take it or leave it).
One constraint, binary variables, a linear objective — it looks tiny. Yet with n
items there are 2^n possible subsets, and knapsack is
NP-hard.
The art is finding the best subset without inspecting all 2^n of them.
Why greedy can fail
The obvious idea is greedy by value-to-weight ratio: sort items by
v_i / w_i and grab the "best bang per kilo" first. It is fast, it feels
right — and for the 0/1 knapsack it can be wrong. Take capacity W = 6 and
three items:
| Item | Value | Weight | Ratio v/w |
|---|
| 1 | 6 | 3 | 2.00 |
| 2 | 6 | 3 | 2.00 |
| 3 | 5 | 2 | 2.50 |
Greedy grabs item 3 first (best ratio, weight 2), then item 1 (weight now 5) — and item 2 no longer
fits in the remaining 1 unit. Greedy's haul is 5 + 6 = 11. But the
optimal choice ignores the shiny ratio and takes items 1 and 2 together: weight exactly
6, value 6 + 6 = 12. Greedy left value on the
table because one high-ratio item wasted capacity that a better combination needed.
(Curiously, if you were allowed to take fractions of items — the "fractional knapsack" — greedy
by ratio is optimal. It is the indivisibility, the 0/1, that breaks it.)
The dynamic-programming solution
The reliable method is dynamic programming. Build a table
T[i][c] = the best value achievable using only the first
i items with a sack of capacity c. Each cell asks
one question: for item i, is it better to leave it or
take it?
T[i][c] = \max\Big(\; \underbrace{T[i-1][c]}_{\text{leave item } i},\;\; \underbrace{v_i + T[i-1][\,c - w_i\,]}_{\text{take item } i\ (\text{if } w_i \le c)} \;\Big)
Fill the grid row by row; the answer is the bottom-right cell,
T[n][W]. Below is that table for our three items and
W = 6 — step through it and watch each row build on the one above:
The final cell reads 12 — the true optimum, recovered without ever
enumerating all 2^3 = 8 subsets. To recover which items were taken,
walk back up the table: whenever a cell differs from the one directly above it, that row's item was
taken.
Run the algorithm yourself
Here is the whole method in a few lines. The compact loop uses a one-dimensional table and counts
capacity downward so each item is used at most once (the 0/1 rule); it then also prints the full
O(nW) grid so you can see the row-by-row build. Press Run:
// 0/1 knapsack by dynamic programming.
const values = [6, 6, 5];
const weights = [3, 3, 2];
const W = 6;
const n = values.length;
// Compact 1-D version: dp[c] = best value for capacity c.
const dp: number[] = new Array(W + 1).fill(0);
for (let i = 0; i < n; i++) {
// Count capacity DOWN so item i is added at most once.
for (let c = W; c >= weights[i]; c--) {
const take = values[i] + dp[c - weights[i]];
if (take > dp[c]) dp[c] = take;
}
}
console.log("Optimal value for capacity " + W + " = " + dp[W]);
// Full table T[i][c] to show the O(n*W) grid.
const T: number[][] = [];
for (let i = 0; i <= n; i++) T.push(new Array(W + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let c = 0; c <= W; c++) {
T[i][c] = T[i - 1][c]; // leave item i
if (weights[i - 1] <= c) { // or take it
const take = values[i - 1] + T[i - 1][c - weights[i - 1]];
if (take > T[i][c]) T[i][c] = take;
}
}
}
console.log("capacity: 0 1 2 3 4 5 6");
for (let i = 0; i <= n; i++) console.log("row " + i + ": " + T[i].join(" "));
The last line of output is the table you just stepped through, ending in the optimum
12.
The DP fills an n \times (W+1) table, so it runs in
O(nW) time — that looks fast, even polynomial. The catch is
W. A capacity like 1{,}000{,}000 is written with
only 7 digits, yet the table has a million columns: the running time is polynomial in the
value W but exponential in the number of bits used
to write it down. That "polynomial in the number, not its size" is exactly what
pseudo-polynomial means. It is why knapsack DP is wonderful for modest capacities and
useless for astronomically large ones — and why knapsack stays NP-hard despite having such a tidy
algorithm.
The two problems look like twins and behave nothing alike. In the fractional knapsack
you may slice items, and the simple greedy-by-ratio rule is provably optimal and runs in
O(n\log n). In the 0/1 knapsack items are indivisible,
greedy is not optimal (as we saw), and you need dynamic programming or branch and bound. If an
exam or a solver "just sorts by ratio and stops", it is silently solving the fractional problem — a
different, easier problem whose answer can exceed the true 0/1 optimum. Always ask first: can the items
be split?