Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Given items with weights and values and a capacity W, maximize total value where each item is taken at most once. The recurrence is dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]]) — either skip item i or take it. Naive recursion is O(2ⁿ); memoize on (i, w) or build a 2-D table for O(nW). Then collapse to a 1-D dp[w] and iterate weight DESCENDING so each item is used once.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you model a constrained optimization as a 2-D DP over (items, capacity), derive the take-or-skip recurrence cleanly, and know why the 1-D space optimization must iterate capacity backwards.
Where candidates slip
Iterating weight ascending in the 1-D version (silently allows reusing an item, computing the unbounded answer), or reading the current row instead of the previous row in the take branch.
How to stand out
Derive the recurrence from the include/exclude decision, show the 2-D table, then collapse to 1-D and explain — out loud — that descending order is what enforces 'each item once'. Name the parent pattern and its children (Subset Sum, Partition, Target Sum).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMaximize value under capacity WItems reusable or once each?ReusableOnce eachExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recursive Include/Exclude
1Hint 1Explore hintHide hint
Focus on the LAST item. You only ever do one of two things with it: leave it out, or put it in. What subproblem remains in each case?
2Hint 2Explore hintHide hint
If you skip item i, you must still fill capacity w from items 0..i-1. If you take it (only when weight[i] ≤ w), you gain value[i] and fill w - weight[i] from items 0..i-1.
3Hint 3Explore hintHide hint
knap(i, w) = max(knap(i-1, w), value[i] + knap(i-1, w - weight[i])). Base case: no items left (i < 0) → value 0.
A · Core idea
Decide the items one at a time, from the last index down to the first. For item i there are exactly two futures: exclude it and solve the same capacity w using items 0..i-1, or include it (only legal when weight[i] <= w), collect value[i], and solve the reduced capacity w - weight[i] using items 0..i-1. The answer for (i, w) is the larger of those two.
The mental shift: one binary decision, then recurse on a smaller item set. Don't try to choose the whole subset at once. Commit to a single item's fate, shrink the problem by one item, and let recursion handle the rest. Because the include branch recurses on i-1 (not i), the same item can never be picked twice — that single detail is what encodes the '0/1' rule.
Why the take branch is guarded by `weight[i] <= w`. You can't put an item into a knapsack that no longer has room for it. If weight[i] > w, the take branch is simply unavailable and only the skip branch survives — there's no negative-capacity subproblem.
Why max, not sum. We're choosing the best of two mutually exclusive plans (with vs without item i), so we combine them with max. Summing would double-count plans that are alternatives, not companions.
Why we don't ship this. The same (i, w) state is reached through enormously many take/skip orderings, so the tree recomputes it over and over — exponential overlap. Cache the answer per (i, w) and the blowup collapses.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
weight = [1, 3, 4], value = [1, 4, 5], W = 4knap(2, 4)
skip → knap(1,4); take (wt4≤4) → 5 + knap(1,0)
branches out5C · Code with teaching comments
Reference implementation previewpublic int knapsack(int[] weight, int[] value, int W) { return solve(weight, value, weight.length - 1, W); } private int solve(int[] weight, int[] value, int i, int w) {Explore the full codeHide the full code
D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The state is fully described by two numbers: how many items remain to decide (i) and how much capacity is left (w). Two small state variables plus massive recomputation is the textbook signal to memoize over a 2-D grid.
ComplexityO(2ⁿ) time, O(n) space — Every item forks into take/skip, so the recursion tree has up to 2ⁿ leaves. Each node does O(1) work. Recursion depth is n, giving O(n) stack space.
E · Edge cases and pitfalls4W = 0 — Every take branch is blocked (weight ≥ 1 > 0), so every path returns 0 — empty knapsack.Explore edge casesHide edge cases
Edge cases handled
W = 0Every take branch is blocked (weight ≥ 1 > 0), so every path returns 0 — empty knapsack.
Pitfalls
- Recursing on i (not i-1) in the take branch — lets an item be reused, which solves unbounded knapsack instead.
- Forgetting the weight[i] <= w guard — produces a negative-capacity subproblem.
- Skipping this approach as 'too obvious' — the include/exclude recurrence is exactly what the interviewer wants you to verbalize first.
Approach 2 of 3
Top-Down Memoization on (item, capacity)
1Hint 1Explore hintHide hint
solve(i, w) returns the same value every time it's called with the same arguments. Where can you store it so each pair is computed once?
2Hint 2Explore hintHide hint
Use a 2-D memo of size n × (W+1), indexed by item and remaining capacity. Check it on entry; fill it before returning.
3Hint 3Explore hintHide hint
memo[i][w] = max(skip, take). Use a sentinel like -1 for 'uncomputed' since 0 is a legitimate answer.
A · Core idea
Keep the take-or-skip recurrence, but cache solve(i, w) in a 2-D table so every (item, capacity) pair is solved exactly once. The memo starts 'uncomputed'; on entry we return the cached value, and we store the result before returning.
The mental shift: the future depends only on (i, w). Whatever sequence of take/skip choices led here, the remaining decisions depend solely on which items are still undecided (i) and how much room is left (w). Two different paths that both reach (2, 5) have identical futures, so caching by (i, w) collapses all those duplicate subtrees into one computation. The number of distinct states — n × (W+1) — is exactly the time bound.
Why a 2-D memo, not 1-D. Unlike Coin Change (where the only state is the remaining amount), here the answer genuinely depends on both the item index and the capacity, because which items are still available changes the answer. Drop the i dimension and you'd conflate states with different remaining item sets.
Why -1 as the sentinel. A value of 0 is a perfectly valid answer (nothing fits), so 0 cannot mean 'uncomputed'. Initialize the memo to -1 and treat that as the empty marker.
A language note worth saying out loud. This top-down form recurses up to n deep. In Java that's fine for n ≤ 100. In Python the default recursion limit is about 1000, so deep top-down DP can hit RecursionError on large inputs — which is exactly why the bottom-up table (next approach) is the safer default in Python.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
weight = [1, 3, 4, 5], value = [1, 4, 5, 7], W = 7solve(3, 7)
skip → solve(2,7); take wt5 → 7 + solve(2,2)
memo empty9C · Code with teaching comments
Reference implementation previewpublic int knapsack(int[] weight, int[] value, int W) { int n = weight.length; int[][] memo = new int[n][W + 1]; for (int[] row : memo) { Arrays.fill(row, -1);Explore the full codeHide the full code
D · Why it works and complexityO(nW) timeO(nW) spaceOpen the invariant and proofExplore the proofHide the proof
Memoization is the same mechanical upgrade as every DP: a correct recurrence plus a cache keyed on the true state. The intellectual work was recognizing that (item index, remaining capacity) is the complete state — once you see that, the table writes itself, and its size is your time complexity.
ComplexityO(nW) time, O(nW) space — There are n × (W+1) distinct (i, w) states. Each is computed once with O(1) work → O(nW) time. The memo table is O(nW); recursion depth is O(n) on top of that.
E · Edge cases and pitfalls5W = 0 — Every take branch is blocked; memo[i][0] = 0 for all i — returns 0.Explore edge casesHide edge cases
Edge cases handled
W = 0Every take branch is blocked; memo[i][0] = 0 for all i — returns 0.single item heavier than Wsolve(0, W) can't take it, recurses to solve(-1, W) = 0 → answer 0.
Pitfalls
- Using 0 as the 'uncomputed' sentinel — collides with the valid answer 0; use -1.
- Sizing the memo as W instead of W+1 — capacity 0..W is W+1 distinct columns.
- In Python, deep top-down recursion can exceed the ~1000 recursion limit on large n — tabulation avoids the stack entirely.
Approach 3 of 3 · Optimal
Bottom-Up Table + 1-D Space Optimization (Optimal)
1Hint 1Explore hintHide hint
Instead of recursing, fill a grid dp[i][w] = best value using the first i items within capacity w. dp[0][*] = 0.
2Hint 2Explore hintHide hint
For each item i and each capacity w: dp[i][w] = dp[i-1][w] if it doesn't fit, else max(dp[i-1][w], value[i-1] + dp[i-1][w - weight[i-1]]).
3Hint 3Explore hintHide hint
Each row only reads the row above, so you can keep a single dp[w]. To still read the 'previous item' values, iterate w from W DOWN to weight[i] — descending order keeps dp[w - weight] referring to the old (item not yet taken) value.
A · Core idea
Build the answers from the ground up in a grid where dp[i][w] is the best value obtainable from the first i items within capacity w. Row 0 (no items) is all zeros. For each later item, every cell asks the same take-or-skip question as the recursion, but now both subproblems are already sitting in the row directly above.
The 2-D recurrence, in table terms. For item i (1-indexed into the table) with weight wt and value val: if wt > w the item can't fit, so dp[i][w] = dp[i-1][w] (inherit the skip value). Otherwise dp[i][w] = max(dp[i-1][w], val + dp[i-1][w - wt]) — the best of skipping versus taking. The answer is dp[n][W].
Collapsing to one row. Notice dp[i][*] only ever reads dp[i-1][*]. That means we don't need the whole grid — a single array dp[w] that we overwrite per item is enough, if we're careful about order.
Why the 1-D loop must go DESCENDING — the crux of the whole problem. When we process item i over a single array, dp[w - wt] must still hold the value from before this item was considered (the dp[i-1] row). If we iterate w ascending, we'd update dp[w - wt] first and then read it at dp[w] — meaning item i could be counted a second time, which is the unbounded knapsack answer. Iterating w from W down to wt guarantees dp[w - wt] is still the old value when we read it, so each item is used at most once. This single loop direction is the entire difference between 0/1 and unbounded knapsack.
Why dp[0] stays 0. With no items chosen, every capacity yields value 0; that bottom row anchors all the maxima above it, just as dp[0]=0 anchors Coin Change.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
weight = [1, 3, 4, 5], value = [1, 4, 5, 7], W = 7Array state
init
no items chosen
9C · Code with teaching comments
D · Why it works and complexityO(nW) timeO(W) spaceOpen the invariant and proofExplore the proofHide the proof
0/1 Knapsack is the root of a whole family — Subset Sum, Partition Equal Subset Sum, Target Sum, Last Stone Weight II are all this exact grid with the objective swapped (feasibility, equality, count). And the descending 1-D sweep is the portable trick: ascending = reuse allowed (unbounded), descending = once each (0/1). Memorize that one sentence and you can re-derive half the DP catalogue.
ComplexityO(nW) time, O(W) space — The 2-D table has n × (W+1) cells, each filled in O(1) → O(nW) time. Because every row depends only on the one above it, a single rolling array of size W+1 suffices → O(W) space, no recursion stack.
E · Edge cases and pitfalls7W = 0 — Inner loop never runs (W < weight[i]); dp stays all zeros → answer 0.Explore edge casesHide edge cases
Edge cases handled
W = 0Inner loop never runs (W < weight[i]); dp stays all zeros → answer 0.all items heavier than WNo w satisfies w >= weight[i], dp untouched → 0.single item with weight == Wdp[W] = max(0, value) = value — the item exactly fills the bag.
Pitfalls
- Iterating weight ASCENDING in the 1-D version — silently computes the unbounded answer by reusing items.
- Reading dp[i][w - wt] (current row) instead of dp[i-1][w - wt] in the 2-D version — also reuses the item.
- Off-by-one on the table size — use (n+1) × (W+1) and map item i to weight[i-1].
- Looping w only down to 0 in the 1-D version — fine, but stopping at weight[i] is cleaner and avoids a negative index check.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int knapsack(int[] weight, int[] value, int W) { int n = weight.length; int[][] dp = new int[n + 1][W + 1]; for (int i = 1; i <= n; i++) { int wt = weight[i - 1];Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Ascending weight loop in the 1-D version
Iterating w from low to high updates dp[w - weight] before you read it, so the same item is folded in twice — that's unbounded knapsack, not 0/1. Descending order preserves the previous-item values.
Explore the code comparisonHide the code comparison
Ascending weight loop in the 1-D version
Iterating w from low to high updates dp[w - weight] before you read it, so the same item is folded in twice — that's unbounded knapsack, not 0/1. Descending order preserves the previous-item values.
Don't write this
for (int i = 0; i < weight.length; i++) {
for (int w = weight[i]; w <= W; w++) { // ASCENDING — wrong for 0/1
dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
}
}Write this instead
for (int i = 0; i < weight.length; i++) {
for (int w = W; w >= weight[i]; w--) { // DESCENDING — each item once
dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
}
}2Reading the current row in the 2-D take branch
dp[i][w - wt] is being computed in this same pass, so it may already include item i — reusing it. The take branch must read dp[i-1], the previous item's row.
Explore the code comparisonHide the code comparison
Reading the current row in the 2-D take branch
dp[i][w - wt] is being computed in this same pass, so it may already include item i — reusing it. The take branch must read dp[i-1], the previous item's row.
Don't write this
dp[i][w] = max(dp[i - 1][w], val + dp[i][w - wt])Write this instead
dp[i][w] = max(dp[i - 1][w], val + dp[i - 1][w - wt])3Sentinel collides with a valid 0
An empty or all-too-heavy knapsack scores 0, so 0 cannot also mean 'this memo cell is unfilled'. Use -1 (or a separate boolean grid).
Explore the code comparisonHide the code comparison
Sentinel collides with a valid 0
An empty or all-too-heavy knapsack scores 0, so 0 cannot also mean 'this memo cell is unfilled'. Use -1 (or a separate boolean grid).
Don't write this
int[][] memo = new int[n][W + 1]; // defaults to 0
if (memo[i][w] != 0) return memo[i][w];Write this instead
int[][] memo = new int[n][W + 1];
for (int[] row : memo) Arrays.fill(row, -1);
if (memo[i][w] != -1) return memo[i][w];Revise
Carry the pattern into the interview
Pattern to remember
0/1 knapsack — take-or-skip on a 2-D (item, capacity) grid
Code pattern to memorize
dp[i][w] = dp[i-1][w] # skip item i
= max(that, val[i] + dp[i-1][w - wt[i]]) # take item i, if wt[i] <= w
1-D: for each item, for w from W down to wt[i]: dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Rules to remember
- 1Two choices per item: skip (carry
dp[i-1][w]) or take (val[i] + dp[i-1][w - wt[i]]). Take is only legal whenwt[i] <= w. - 2Each item is used at most once — that's the '0/1'. The take branch reads row
i-1, never rowi, so it can't reuse the same item. - 3In the 1-D optimization, iterate weight DESCENDING (
W → wt[i]). Ascending would let an item be picked twice, turning it into unbounded knapsack. - 4Initialize
dp[0][*] = 0anddp[*][0] = 0— zero items or zero capacity yields zero value. - 5Answer is
dp[n][W]. The grid is(n+1) × (W+1); the off-by-one from the empty-prefix row 0 trips people up.
Use this pattern when
- Pick a subset to maximize value under a single capacity/budget constraint
- Each item is available exactly once (no repeats)
- Two-way decision per element: include it or leave it
- Constraint and values are small enough that O(nW) is affordable (pseudo-polynomial)
Choose another pattern when
- Items reusable unlimited times → unbounded knapsack, iterate weight ASCENDING
- You only need feasibility (does a subset hit an exact sum?) → Subset Sum boolean DP
- Capacity W is astronomically large → O(nW) is too big; consider meet-in-the-middle or branch-and-bound
- Fractions of an item allowed → greedy by value/weight ratio (fractional knapsack), not DP
Interview takeaway
0/1 Knapsack is the parent of an entire family. Burn the take-or-skip recurrence into memory: dp[i][w] = max(skip, value + dp[i-1][w - weight]). Subset Sum, Partition Equal Subset Sum, Target Sum, and Last Stone Weight II are all this same grid with the objective swapped. The DESCENDING 1-D sweep is the single trick that separates 0/1 from unbounded.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical 0/1 knapsack — the root of the take-or-skip DP family. Recognize it whenever you choose a subset to optimize value under one capacity constraint with each item usable once. Same grid powers Subset Sum, Partition Equal Subset Sum, Target Sum, and Last Stone Weight II; the descending 1-D sweep is what makes it '0/1' rather than unbounded.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Partition Equal Subset SumComing soon0/1 knapsack on feasibility: can a subset hit exactly total/2? Boolean dp[w], iterate descending.
- Target SumComing soonAssign + or − to each number — reduces to counting subsets with a fixed sum, a 0/1 knapsack count DP.
- Last Stone Weight IIComing soonSplit stones into two groups with minimal difference — a 0/1 knapsack maximizing weight up to total/2.
- Unbounded KnapsackSame value-maximizing setup but items are reusable — flip the 1-D weight loop to ascending.