0/1 Knapsack —
Every item, one binary choice: take it or don't.
Given items with weights and values and a weight limit, maximize total value without exceeding the limit — each item can only be taken whole or left behind, never split. This is the first 2D DP table on this hub: one axis for items considered, one for weight capacity. Watch each cell fill in on LearnBug and see the include/skip decision made explicit.
What is 0/1 Knapsack?
dp[i][w] holds the best possible value using only the first i items, within weight capacity w. For each item, you either skip it (dp[i-1][w], unchanged) or include it (dp[i-1][w - weight] + value, if it fits) — take whichever is larger. "0/1" means each item is used at most once, unlike Coin Change's unlimited coin supply.
Why visualization helps
This is the first 2D table on this hub — rows for items, columns for capacity — and it's easy to lose track of which row and column a given cell depends on. LearnBug highlights the two candidate cells (skip vs include) that feed into each new cell, so the "compare, take the max" logic is visibly anchored to specific earlier cells, not the whole table at once.
Why this needs a table, not just an array
Rows: which items are "in consideration"
Row i represents "using only the first i items." Row 0 (no items) is trivially all zeros — the base case for every column.
Columns: remaining weight capacity
Column w represents "if the bag can hold up to w weight." Column 0 (no capacity) is also trivially all zeros.
Each cell: max(skip, include)
Every cell only ever looks at two specific cells from the row above — never anywhere else in the table — comparing "don't take this item" vs "take it."
Items (w=[1,3,4,5], v=[1,4,5,7]), capacity 7
Row 1 (item 1: weight 1, value 1) — fits in every capacity ≥ 1, so it's always taken
dp[1][0]=0 (no room). For every w ≥ 1: skip gives dp[0][w]=0, include gives dp[0][w-1]+1=1. Include always wins, so dp[1][w]=1 for all w from 1 to 7.
Row 2 (item 2: weight 3, value 4) — at w=3, compare skip (1) vs include (0+4=4). Include wins
Skip: dp[1][3] = 1 (just item 1). Include: dp[1][3-3] + 4 = dp[1][0] + 4 = 0 + 4 = 4. Taking item 2 alone beats keeping item 1 — 4 > 1.
Row 3 (item 3: weight 4, value 5) at w=7 — compare skip (dp[2][7]) vs include (dp[2][3]+5)
dp[2][7] = 5 (items 1+2: weight 4, value 5). Include item 3: dp[2][7-4] + 5 = dp[2][3] + 5 = 4 + 5 = 9. Including item 3 wins.
Row 4 (item 4: weight 5, value 7) at w=7 — compare skip (9) vs include (dp[3][2]+7 = 1+7 = 8)
dp[3][2] = 1 (only item 1 fits in weight 2 at this row). Including item 4: 1 + 7 = 8, which is less than skipping (9). Skip wins this time.
Return: dp[4][7] = 9 ✓ items 1+2+3 (weights 1+3+4=8... recheck: 1+3=4, +weight4=8>7) — actual best is items 1+3 (w=1+4=5≤7, v=1+5=6) vs items 1+2 (w=1+3=4, v=1+4=5) vs item 2+3 (w=3+4=7, v=4+5=9) ✓ matches 9
2D bottom-up DP table
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # SKIP item i — carry the row above forward
if weights[i - 1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1] # INCLUDE item i
)
return dp[n][capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(knapsack(weights, values, 7)) # 9Complexity Notes
Frequently asked questions
Why does each cell only need the row directly above it, not the whole table?
Because dp[i][w] is only ever defined in terms of dp[i-1][...] — "what was possible using one fewer item." Once row i is fully computed, row i-1 is never referenced again, which is exactly why the table can be optimized to a single rolling row of size W instead of the full n × W grid.
Why is it called "0/1" specifically?
Each item's inclusion is a binary choice — 0 (leave it out) or 1 (take the whole item) — with no fractional amounts allowed and no repeats. This distinguishes it from the Fractional Knapsack problem (where items can be split, solvable greedily) and from Coin Change's unbounded version (where "items" — coins — can repeat any number of times).
Why must the weights array be iterated in a specific loop order?
The outer loop over items must come before the inner loop over capacity precisely because each item can only be used once — this ensures dp[i-1][...] never includes item i itself. If you collapse this to a 1D array (the space-optimized version), you must also iterate capacity in reverse to preserve this "used at most once" guarantee.
How would I recover which specific items were chosen, not just the max value?
Trace backward from dp[n][capacity]: at each step, if dp[i][w] != dp[i-1][w], item i was included — subtract its weight and move to dp[i-1][w - weight]; otherwise it was skipped and you move to dp[i-1][w] unchanged. Walking this path from the final cell back to row 0 reconstructs the exact set of chosen items.
Watch each cell decide: include this item, or skip it
Paste 0/1 knapsack into LearnBug and see the 2D table fill in, row by row.