0/1 Knapsack
Given item weights and values and a knapsack capacity, maximise the total value carried. Each item may be taken at most once.
Open on GeeksforGeeks ↗Intuition
Greedy by value-to-weight ratio is the natural first instinct and it is wrong here, because capacity must be packed as a whole rather than filled proportionally — a slightly worse ratio can fit the remaining space exactly. Instead ask one binary question per item: take it or skip it. Skipping leaves the same capacity with fewer items; taking spends its weight and leaves a strictly smaller capacity. Both branches are smaller subproblems, so a table over (items considered, capacity) solves each exactly once.
The template every take-or-skip DP is built from. Each item is used at most once, so the state is (items considered, capacity remaining) and each cell picks the better of two options. Recognising the 0/1 shape — indivisible items, one use each — is what tells you greedy will fail and a table is required.
Approach
Two-dimensional state
dp[i][c] = best value using only the first i items within capacity c. Row 0 is all zeros — no items, no value.
Take or skip
If the item fits, dp[i][c] = max(skip, take) where skip = dp[i-1][c] and take = value[i] + dp[i-1][c - weight[i]]. If it does not fit, only skip is available.
Why the previous row
Both branches read row i-1, never row i. That is exactly what enforces 'at most once' — an item can never be consulted after it has been taken.
Solution & live demo
Common pitfalls
Sorting by value-to-weight ratio and taking greedily
items.sort(key=lambda x: x[0] / x[1], reverse=True)
for v, w in items:
if cap >= w: total += v; cap -= wdp[i][c] = max(skip, take)
That's the fractional knapsack solution, and it fails here: with capacity 4 and items (value 3, weight 3) and (value 4, weight 4), the better ratio takes the 3 and wastes a unit. Indivisible items break the exchange argument that makes greedy safe.
Indexing weights with the table index
if wt[i] <= c:
take = val[i] + dp[i - 1][c - wt[i]]if wt[i - 1] <= c:
take = val[i - 1] + dp[i - 1][c - wt[i - 1]]Row i means "the first i items", so the item it just added sits at array position i - 1. Using i directly reads the next item and runs off the end on the last row.
Considering take when the item doesn't fit
take = val[i-1] + dp[i-1][c - wt[i-1]] dp[i][c] = max(skip, take)
if wt[i - 1] <= c:
dp[i][c] = max(skip, take)
else:
dp[i][c] = skipA negative capacity index wraps to the far end of the row in Python, silently mixing in a value from an unrelated state. An item heavier than the remaining capacity has exactly one option — skip.
Edge cases
Column 0 stays 0 — nothing fits, so no value is achievable.
weight > c in every column, so the value is inherited unchanged from the row above.
Every take branch wins and the answer is the sum of all values.