The site's third dynamic programming entry, and the first that isn't about aligning two strings. The question here is a literal packing problem: given a set of items, each with its own weight and value, and a knapsack that can carry at most a fixed total weight, which items should go in to make the total value as large as possible? Every item is all-or-nothing — take it whole or leave it behind, no splitting a tent in half to save a kilogram, which is what the "0/1" in the name refers to. It sounds like a fresh kind of problem, but the table this page builds is filled in exactly the way Longest Common Subsequence and Edit Distance fill theirs: solve every smaller subproblem first, in an order that guarantees everything a cell needs already sits in the table by the time it's computed.
Five fixed items for a hiking pack and a capacity of 10 (the units don't matter — call them
kilograms), not user-editable, same convention as this site's other fixed-content interactive demos. Press
Step or Run to watch the table fill in: each cell dp[i][w] holds
the best total value achievable using only the first i items with a knapsack of capacity
w. Once the table is full, the demo backtracks from the bottom-right corner, working out which
items actually made it into the optimal pack — watch the item chips below confirm each one in or out.
Row 0 is the base case: with zero items available, the best value at any capacity is 0 —
there's nothing to choose from yet, so dp[0][w] = 0 for every w. That's the entire
top row, filled before any real decision happens.
Every other cell asks one yes-or-no question: does item i go into a knapsack of capacity
w? If item i's weight is more than w, there's no choice at all — it
simply can't fit, so dp[i][w] = dp[i-1][w], whatever the best value was without it. If it does
fit, there's a real decision, and the recurrence tries both answers and keeps the better one:
skip it (dp[i-1][w], unchanged) or take it (its own value,
plus whatever capacity w - weighti could best achieve using only the items already
decided, valuei + dp[i-1][w - weighti]).
dp[i][w] = max(skip, take). Every subproblem a cell needs — the row above, at either the same
capacity or a smaller one — is already filled in by the time that cell is computed, the same
optimal-substructure argument
Longest Common Subsequence and
Edit Distance both make, just with a real
either/or decision per cell instead of a fixed menu of edit options.
Builds the table bottom-up, then walks it backward from the bottom-right corner to recover which items were actually chosen — not just the best total value:
function knapsack(items, capacity) {
const n = items.length;
const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
const { weight, value } = items[i - 1];
for (let w = 0; w <= capacity; w++) {
if (weight > w) {
dp[i][w] = dp[i - 1][w]; // doesn't fit, no choice but to skip
} else {
dp[i][w] = Math.max(dp[i - 1][w], value + dp[i - 1][w - weight]);
}
}
}
// backtrack from the bottom-right corner to recover which items were taken
let i = n, w = capacity;
const chosen = [];
while (i > 0) {
if (dp[i][w] === dp[i - 1][w]) {
// value didn't change by considering item i — it wasn't used
i--;
} else {
chosen.push(items[i - 1]);
w -= items[i - 1].weight;
i--;
}
}
chosen.reverse();
return { maxValue: dp[n][capacity], chosen };
}
The table gives one optimal value, not one canonical optimal set. On this page's own
demo data, two different packs both total exactly 22: Tent + Food (weight
10) and Stove + Rope + Water (also weight 10). The backtrack step above
resolves every tie the same deterministic way — dp[i][w] === dp[i-1][w] is checked first, so any
cell where skipping ties with taking gets reported as "skipped" — which is why the demo always recovers
Tent + Food and never the other pack, even though both are equally valid answers. It's the same
caveat Longest Common Subsequence and
Edit Distance already raise about their own
backtracking ties: the number is never ambiguous, the reconstructed answer can be.
Sorting by value-per-weight and greedily grabbing the best ratio first — the approach that
actually works for the fractional knapsack
problem, where items can be split — fails here.
Ranking this page's five items by value/weight puts Stove first (8/3 ≈ 2.67), then Food, then
Tent, then Rope and Water tied. Greedily filling the pack in that order takes Stove, then Food, then Rope
(total weight 9, value 21) before running out of room for anything else — a real,
worse answer than the table's 22. Not being able to take 0.6 of an item is exactly what breaks
the greedy argument: a slightly-too-heavy high-ratio item can force leaving capacity unused that two
lower-ratio items would have filled better together. See
Fractional Knapsack, which reuses this exact dataset to
show the identical ratio-greedy rule succeeding once splitting is allowed.
Compressing the table to a single row of size capacity + 1 is possible, unlike the
row-pair trick Longest Common Subsequence
and Edit Distance use — but only if the inner loop runs capacity downward, from
capacity to weighti. Every dp[i][w] only ever
reads row i-1 at column w or lower, so one row can stand in for the whole table as
long as it's updated in place. Filling that row left-to-right, though, would let a cell read a value this
same row already overwrote for item i — silently letting item i get used a second
time in the same pass, turning 0/1 knapsack into the different (and easier) unbounded-knapsack problem, where each item can be taken
any number of times. Iterating w downward guarantees every read still comes from the
previous item's row, never this one.
O(n · capacity) looks polynomial, but it isn't, quite. The bound depends on
the numeric value of the capacity, not the size of its representation — writing "1,000,000" takes seven
characters but produces a million-column table. Double every weight, value, and the capacity, and the
problem is identical in every meaningful sense, but the table this page builds would have twice as many
columns. Algorithms whose cost scales with a number's magnitude rather than its input size are called
pseudo-polynomial — genuinely fast enough at the sizes this page's demo runs at, but not a
counterexample to 0/1 knapsack's status as a classic NP-hard problem in general.
The claims above are stated but never run at any scale past this page's own 5-item, capacity-10 demo.
Running the page's own shipped knapsack() function, completely unchanged, at growing capacities
makes both claims concrete instead of hypothetical.
Doubling every weight, value, and capacity really is the identical problem, just bigger — and
the table really does double with it. Scaling this page's own five items and capacity 10 by a
factor k (factor 2 → weights/values/capacity ×2, and so on) always recovers the exact same
pack (Tent + Food) and a max value that scales by the same k:
| factor | capacity | cells | max value | chosen |
|---|---|---|---|---|
| 1× | 10 | 66 | 22 | Food, Tent |
| 2× | 20 | 126 | 44 | Food, Tent |
| 4× | 40 | 246 | 88 | Food, Tent |
| 8× | 80 | 486 | 176 | Food, Tent |
| 16× | 160 | 966 | 352 | Food, Tent |
Same five decisions every time, same answer scaled exactly — but twice the cells (and, at real scale, twice the work) for a problem that is "the same" in every sense that matters to whoever is packing the bag.
Scaling the capacity (a number) costs far more than scaling the item count (the actual input
size) by the same factor. Holding n = 5 items fixed and scaling capacity by
powers of 10 — adding one decimal digit to how the capacity is written — multiplies the real cell
count and wall-clock time by roughly 10× at every step, not by a few extra characters' worth of work:
| capacity | digits | cells | time |
|---|---|---|---|
| 10 | 2 | 66 | 0.04 ms |
| 1,000 | 4 | 6,006 | 0.44 ms |
| 100,000 | 6 | 600,006 | 17.9 ms |
| 10,000,000 | 8 | 60,000,006 | 870.9 ms |
Compare that against scaling n instead, by a far larger factor (5 items up to 50,000 — 10,000×
the input size) at a small fixed capacity of 50: cell count only reaches 2,550,051 and wall-clock only
74.9 ms — cheaper than capacity 10,000,000's single run above, despite a 10,000× larger input in the
dimension that's actually supposed to drive an algorithm's cost. Growing the number by two extra
digits costs more than growing the real input by four orders of magnitude; that gap between "numeric
magnitude" and "input size" is exactly what "pseudo-polynomial" names.
Both tables above were measured once, frozen into this page. The same knapsack() function,
completely unchanged, can run again right now — in whichever browser is reading this, on whatever hardware
that happens to be. Pick a capacity and click Measure to watch the real cell count and wall-clock time come
back from this page's own code, not this page's prose:
knapsack() function, completely unchanged, at that capacity, right now, in your browser, and
reports the real cell count and wall-clock time it takes.Verified: ran the page's own knapsack(), pasted verbatim into a throwaway
Node script, for every row above — no reimplementation, no estimate. n=50,000 is the largest
item count tried; capacity=10,000,000 is the largest capacity tried (cells ≈6×10⁷, ~870 ms —
further growth was not pursued, but the 10×-per-digit trend across four measured points is already
consistent to visible precision). The widget just above runs this exact same function live, in whatever
browser is reading this page — a second, independent way to see the same growth, not just take the table
on faith.
Time: O(n · W) — one constant-time comparison per cell,
(n+1)(W+1) cells total, where n is the item count and W the capacity.
Space: O(n · W) for the full table (needed to reconstruct which items were
chosen), or O(W) with the downward-iterating single-row compression described in Pitfalls
above, at the cost of losing the ability to backtrack.
Variants of this exact recurrence show up anywhere a fixed budget has to be spent on indivisible choices: cutting a length of raw material into pieces to maximize revenue (the related "rod cutting" problem), allocating a fixed compute budget across jobs with different costs and payoffs, or picking which tasks to schedule in a limited window when each one is worth doing wholly or not at all.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other eleven Dynamic Programming entries side by side. A related but different question — not maximizing value under a weight cap, but deciding whether some subset hits an exact target sum at all — is Subset Sum, solved by searching and backtracking instead of filling a table.