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.
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 ten 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.