Algorithms from zero
0/1 knapsack and subset sum: maximize value within a weight capacity
You are a thief with a bag that holds at most 5 kilograms. In front of you sit items, each with a weight and a value, and you can grab each one only once—it goes in the bag or it stays. Which set of items maximizes the value you walk away with? You cannot just greedily grab the most valuable item; it might be too heavy and crowd out two cheaper items that together beat it. This is the 0/1 knapsack problem, and it is the canonical two-axis dynamic program: one axis is “which items have I considered,” the other is “how much capacity is left.” Get this one, and a whole family of “pick a subset under a budget” problems falls with it—including subset sum, the boolean little brother that just asks: can any subset hit an exact target?
After this lesson you can solve 0/1 knapsack with a DP table: state dp[i][w] is the best value using the first i items within capacity w, and the recurrence at each cell is the max of skip item i (dp[i-1][w]) and take item i (dp[i-1][w-wt[i]] + val[i], only if it fits). You can solve subset sum as the boolean specialization—replace max with OR and value with “reachable.” You can collapse the 2D table to a 1D rolling array, and—this is the subtle, must-not-miss part—you can explain why the inner capacity loop must run downward for 0/1 (so each item is used at most once) and why upward instead gives the unbounded knapsack (items reusable). You can state the time complexity O(n·W) and explain why it is only pseudo-polynomial: W is a numeric value, not a count of inputs, so the cost can blow up even for a tiny item list. Next unit moves from these one-dimensional capacity DPs to harder structures.
The problem, stated precisely
You have n items. Item i has weight wt[i] and value val[i]. You have a knapsack with weight capacity W. Choose a subset of items so the total weight is at most W and the total value is as large as possible. “0/1” means each item is either fully in (1) or fully out (0)—no fractions, no duplicates.
Why greedy fails
The tempting greedy idea—grab the highest value, or the best value-per-weight, until the bag is full—does not work for 0/1. A single high-density item can block a better combination of others. Example: capacity 5, items (wt 2, val 3), (wt 3, val 4), (wt 4, val 5). The best value-per-weight item is the first (1.5 per kg), but the optimal answer takes items 1 and 2 for weight 5 and value 7—beating any single grab. You need to consider combinations, and that is what DP does.
The state and the recurrence
Define the state as a 2D table:
dp[i][w] = the maximum value achievable using only the first i items,
with total weight not exceeding w.For each item i (the i-th item, 1-indexed) and each capacity w, you face exactly two choices:
- Skip item i. Then the best you can do is whatever
dp[i-1][w]already was—the same capacity, one fewer item to consider. - Take item i (only legal if it fits,
wt[i] <= w). You spendwt[i]of capacity and gainval[i], on top of the best you could do with the firsti-1items in the remaining capacity:dp[i-1][w - wt[i]] + val[i].
Take the better of the two:
dp[i][w] = max( dp[i-1][w], // skip item i
dp[i-1][w - wt[i]] + val[i] ) // take item i (if wt[i] <= w)The “take” branch reaches into row i-1, not row i. That is the whole reason each item is used at most once: when you decide about item i, you build on a state that has not yet seen item i.
Base case: dp[0][w] = 0 for every w—with zero items, the best value is 0 regardless of capacity. The answer to the whole problem is dp[n][W].
Filling the table (worked example)
Items (wt 2, val 3), (wt 3, val 4), (wt 4, val 5), capacity W = 5. Rows are items considered (i = 0..3), columns are capacity (w = 0..5):
w=0 w=1 w=2 w=3 w=4 w=5
i=0 0 0 0 0 0 0 no items: all zero
i=1 0 0 3 3 3 3 item (2,3): fits from w=2 on
i=2 0 0 3 4 4 7 item (3,4): w=5 -> take it + dp[1][2]=3 -> 7
i=3 0 0 3 4 5 7 item (4,5): w=5 keeps 7 (skip beats take=5)Read the last cell: dp[3][5] = 7. Trace one interesting cell—dp[2][5]: skip gives dp[1][5] = 3; take gives dp[1][5-3] + 4 = dp[1][2] + 4 = 3 + 4 = 7. Max is 7. The table just discovered “take items 1 and 2.”
Subset sum: the boolean specialization
Subset sum asks a yes/no question: given numbers and a target T, does some subset add up to exactly T? This is 0/1 knapsack where each number is an item whose weight and value both equal the number, and you only care whether a total is reachable. So replace max with logical OR and the value with a boolean “reachable”:
reach[i][t] = true if some subset of the first i numbers sums to exactly t.
reach[i][t] = reach[i-1][t] (skip number i)
OR reach[i-1][t - num[i]] (take number i, if num[i] <= t)Base case reach[i][0] = true (the empty subset sums to 0). The answer is reach[n][T]. Same skip-or-take skeleton, just booleans instead of a running max.
0/1 knapsack with a 2D table
This builds the exact table from the worked example above. Note how every “take” reads from the previous row, dp[i-1].
1
function knapsack(weights, values, W) {
2
const n = weights.length;
3
// dp[i][w] = best value using first i items within capacity w
4
const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
5
6
for (let i = 1; i <= n; i++) {
7
const wt = weights[i - 1];
8
const val = values[i - 1];
9
for (let w = 0; w <= W; w++) {
10
dp[i][w] = dp[i - 1][w]; // skip item i
11
if (wt <= w) { // does item i fit?
12
dp[i][w] = Math.max(
13
dp[i][w],
14
dp[i - 1][w - wt] + val // take item i
15
);
16
}
17
}
18
}
19
return dp[n][W]; // best value, all items, full capacity
20
}
- L4 Row 0 is all zeros (no items = no value); Array.fill(0) sets every cell, so the base case is free.
- L6 Outer loop: bring item i into consideration, one item per row.
- L10 Skip branch: the best without item i is exactly last row's value at the same capacity.
- L11 Take is only legal when the item fits in the current capacity w.
- L13 Take branch reads dp[i-1] (previous row), NOT dp[i] - that is what keeps each item used at most once.
- L19 The answer lives in the bottom-right cell: all n items, full capacity W.
Running it (plus the 1D rolling form and subset sum)
The 2D version, the space-optimized 1D rolling version, and the boolean subset-sum specialization all return the same kind of answer from the same skeleton.
The 1D rolling array and the downward loop
The 2D table only ever reads the previous row, so you do not need to keep all rows—one array dp[w] is enough if you reuse it across items. But there is a catch that decides correctness. After reducing to one array, item i’s update is dp[w] = max(dp[w], dp[w - wt] + val). The cell dp[w - wt] must still hold the value from before item i was processed (the old row i-1). If you sweep w upward (small to large), you would already have updated dp[w - wt] with item i before you read it—so you could add item i to a state that already contains item i, using it twice. Sweeping w downward (large to small) reads dp[w - wt] while it still holds the pre-item-i value, preserving the “at most once” rule. Set the inner loop to for (let w = W; w >= wt; w--) and the 1D version is exactly 0/1 knapsack.
Trace the 1D rolling array on the same items (wt 2, val 3), (wt 3, val 4), (wt 4, val 5) with W = 5. The array starts all zeros, indices 0..5. Watch each item sweep capacity downward so no cell it reads has already absorbed the current item.
1
dp = [0,0,0,0,0,0]; // index 0..W
2
for each item (wt, val):
3
for (w = W; w >= wt; w--) // DOWNWARD
4
dp[w] = max(dp[w], dp[w-wt] + val);
5
return dp[W];
Time: O(n·W)
The 2D version fills an (n+1) x (W+1) table, and each cell does O(1) work (a comparison and at most one addition). Total: O(n·W). The 1D rolling version does the same number of cell updates—n items times up to W capacities—so it is also O(n·W). Subset sum is identical with target T in place of W: O(n·T).
Space: O(W) with the rolling array
The 2D table costs O(n·W) space. But because each row reads only the previous row, the rolling array collapses that to a single array of size W+1: O(W) space (O(T) for subset sum). The trade-off is that you lose the full table, so reconstructing which items were chosen needs extra bookkeeping; if you only need the best value, the rolling array is strictly better.
Why O(n·W) is only “pseudo-polynomial”
This is the crucial subtlety. O(n·W) looks polynomial, but it is not polynomial in the size of the input. The size of the input is the number of bits needed to write it down. The item count n is a genuine count, but W is a numeric value, and a value of W takes only about log2(W) bits to encode. So the running time n·W is exponential in the number of bits of W:
W = 1,000,000 -> ~20 bits to write, but the table has ~1,000,000 columns
double the bits of W (W = 2,000,000) -> the work doubles, not +constantAn algorithm whose cost is polynomial in the numeric value, but exponential in the bit-length of that value, is called pseudo-polynomial. For small W (a few thousand) knapsack is fast and practical. For huge W—say a capacity in the billions with only a handful of items—the table is astronomically large even though the input fits on one line. That is exactly why 0/1 knapsack is NP-complete in general: no algorithm is known that is polynomial in the input size, only in the value W.
Unbounded knapsack: same cost, one loop flipped
Unbounded knapsack (each item reusable any number of times) has the same O(n·W) time and O(W) space. The only code difference is the direction of the capacity loop—upward instead of downward—so that dp[w - wt] is read after it may already include the current item, allowing it to be taken again.
What does the state dp[i][w] represent in 0/1 knapsack?
In the 0/1 knapsack recurrence, the 'take item i' branch is dp[i-1][w - wt[i]] + val[i]. Why does it read row i-1 and not row i?
In the 1D rolling-array version of 0/1 knapsack, why must the inner capacity loop iterate DOWNWARD (from W down to wt)?
What single change to the 1D 0/1 knapsack turns it into the UNBOUNDED knapsack (each item usable any number of times)?
How is subset sum (does any subset sum to exactly T?) a specialization of 0/1 knapsack?
Why is the O(n·W) time of 0/1 knapsack called 'pseudo-polynomial' rather than truly polynomial?
0/1 knapsack with capacity W = 5 and items (wt 2, val 3), (wt 3, val 4), (wt 4, val 5). What is the maximum total value?
An item-count of n = 50 and capacity W = 2000. About how many cells does the 0/1 knapsack DP table have, counting the (n+1) by (W+1) grid as roughly n·W? Give n·W.
Why this works
Why two axes instead of one? Earlier DPs in this unit (Fibonacci, climbing stairs) had a single state variable n. Knapsack needs two because a subproblem is not fully described by “how many items considered” alone—you also need “how much capacity is left,” since the same item set behaves differently at capacity 3 versus capacity 30. Whenever a decision consumes a shared resource (capacity, budget, time), that resource usually becomes a second DP axis. Recognizing “this is a pick-a-subset-under-a-budget problem” is the trigger to reach for the knapsack table.
Common mistake
The upward-loop bug (the classic knapsack mistake). In the 1D version, writing the inner loop as for (let w = wt; w <= W; w++) looks harmless—it even compiles and runs—but it silently solves the wrong problem. Sweeping upward means dp[w - wt] may already include the current item by the time you read it, so the item gets counted multiple times: you have written unbounded knapsack, not 0/1. Concretely, a single item (wt 2, val 3) with capacity 6 returns 3 with the correct downward loop (take it once) but 9 with the upward loop (take it three times). If your 0/1 answer comes out suspiciously large, check the loop direction first.
Edge cases
Capacity exactly zero, and items that do not fit. When W = 0, no item with positive weight fits, so the answer is 0—the base row handles this for free since dp[*][0] stays 0. An item heavier than the whole capacity (wt[i] > W) can never be taken; the if (wt <= w) guard simply skips its “take” branch at every w, so it contributes nothing without special-casing. For subset sum, dp[0] = true is essential: it encodes “the empty subset reaches total 0,” which seeds every reachable total. Forget that one initialization and the whole boolean table stays false.
More practice
Recovering the chosen items. The rolling array gives the best value but not which items were picked. To reconstruct the choice, keep the full 2D table and walk backward from dp[n][W]: at cell dp[i][w], if dp[i][w] == dp[i-1][w] then item i was skipped (move to dp[i-1][w]); otherwise item i was taken (record it, move to dp[i-1][w - wt[i]]). Stop at row 0. This backtracking is O(n) and is the standard way to turn a value-only DP into an actual solution—useful for the subset-sum case too, when you need the subset and not just “yes.”
Explain the 0/1 knapsack DP: the state, the skip-or-take recurrence, how subset sum specializes it, why the 1D rolling loop must run downward, and why the complexity is pseudo-polynomial.
0/1 knapsack maximizes total value over a subset of items whose total weight fits a capacity W, taking each item 0 or 1 times.
State: dp[i][w] = best value using the first i items within capacity w. Answer: dp[n][W].
Recurrence (skip or take):
dp[i][w] = max( dp[i-1][w], // skip item i
dp[i-1][w - wt[i]] + val[i] ) // take it (if wt[i] <= w)Both branches read row i-1, which is what enforces “each item used at most once.”
Subset sum is the boolean specialization: each number is an item with weight = value = the number, and max becomes logical OR over “is this total reachable?” with base case reach[0] = true.
1D rolling array: collapse the table to one array of size W+1. The inner capacity loop must run downward (w from W to wt) so dp[w - wt] still holds the pre-item value—preventing reuse. Flip it to upward and you get the unbounded knapsack (items reusable).
Complexity: time O(n·W), space O(W) with the rolling array. This is pseudo-polynomial: W is a numeric value needing only ~log2(W) bits, so the cost is exponential in the input’s bit-length, not polynomial in input size—which is why 0/1 knapsack is NP-complete in general.
Next unit moves beyond single-capacity DPs to richer state structures.