Don't memorize the knapsack DP — watch the table fill. You have a bag with a weight limit and items each worth something. For every item and every capacity, one question: take it or leave it? A grid remembers the best answer to every smaller version of the problem, so each cell is decided in one comparison — and a trace back reveals exactly which items made the cut.
take or leave · dp[i][w] · traceback · O(n·W)
ITEM
Each has a weight and a value. Take it whole, or not at all.
dp[i][w]
Best value using the first i items within capacity w.
THE CHOICE
max(leave = dp[i−1][w], take = value + dp[i−1][w−weight]).
TRACEBACK
Compare each cell to the one above to see if the item was taken.
A DP table: rows are items, columns are capacities 0…4. Row 0 is “no items”, all zeros. Press Step to add one item per row — each cell takes the better of leaving or taking the item — then trace back the winners.
0
Best value
O(n·W)
Cost
Every subproblem, answered once
Trying every subset of items is O(2ⁿ) — hopeless past a handful. The DP trick is to notice that the best you can do with the first i items and capacity w only depends on the answers for i−1 items. So build a table of every (items, capacity) pair, fill it once from the top, and each cell reuses two cells above it. The last cell, dp[n][W], is the answer — and the path back through the table tells you the items.
01
Leave it
Skip the item: value is whatever you had with the previous items and the same capacity, dp[i−1][w].
02
Take it (if it fits)
Add its value and use the best of the rest with the leftover capacity: value + dp[i−1][w − weight].
03
Keep the max
dp[i][w] = max(leave, take). Fill the whole grid row by row — the answer is the bottom-right cell.
04
Trace back
From dp[n][W]: if a cell equals the one above, the item was left; if not, it was taken — drop its weight and keep going up.
Time
O(n·W)
Space
O(n·W)
Brute force
O(2ⁿ)
Class
NP-hard
This is “pseudo-polynomial”: the runtime depends on the numeric capacity W, not just the item count, so huge capacities are slow (the problem is NP-hard). You can shrink the space to a single row by filling capacities right-to-left. Cousins include unbounded knapsack (unlimited copies), subset sum, and coin change — all the same table with a tweaked recurrence.
SOLVE IT YOURSELF
Solve it: 0/1 knapsack
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
Implement knapsack(weights, values, capacity): pick a subset of items (each usable at most once) whose total weight fits the capacity, maximizing total value. Return that max value. Fill a DP table dp[c] = best value for capacity c — O(n × capacity).
HINTS — 4 IDEAS
Let dp[c] be the best value achievable with a weight budget of c. Start it all zeros.
For each item, decide: skip it (keep dp[c]) or take it (dp[c − weight] + value) — keep the larger.
To use each item only once, sweep the capacity downward (from capacity to weight), so this item is not reused within the same pass.
The answer is dp[capacity] after all items.
CPython · WebAssembly✓ Solved
1
1
Check yourself
1 · What does dp[i][w] represent?
Each cell caches the optimal value for a subproblem — the first i items and a capacity of w.
2 · How is each cell computed?
Take the better of skipping the item or taking it (if it fits) plus the best of the rest with the remaining capacity.
3 · During traceback, a cell equals the cell directly above it. That means:
Equal to the cell above means leaving the item was optimal, so it was not part of the chosen set — move straight up.
Questions
What is the difference from fractional knapsack?
Fractional knapsack lets you take part of an item, which makes a simple greedy (best value-per-weight first) optimal and O(n log n). The 0/1 version forbids fractions, breaks greedy, and needs the DP table.
How do you save memory?
Each row only depends on the previous row, so you can keep a single 1-D array of size W+1 and update it from high capacity down to low — O(W) space instead of O(n·W).
How does coin change relate?
Coin change is knapsack with unlimited copies of each coin and a different objective (fewest coins, or number of ways). Same table shape, the recurrence allows reusing the current row because items are unbounded.
Take it or leave it, one cell at a time.
Fill the grid once, read the answer off the corner, trace back the items. The DP workhorse.