0/1 Knapsack and Space Optimisation
Derive the 0/1 knapsack recurrence, fill the 2D table, then reduce to a 1D array by iterating capacity in reverse.
0/1 Knapsack and Space Optimisation is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The 0/1 Knapsack Problem
The 0/1 Knapsack problem: given n items each with a weight w[i] and value v[i], and a knapsack with capacity W, choose items to maximise total value without exceeding capacity. Each item is taken exactly once (0 = skip, 1 = take). This is the archetype of a large family of interview DP problems including partition-equal-subset-sum and target-sum.
DP State and Recurrence
Define dp[i][c] as the maximum value using the first i items with capacity c. There are two choices for item i: skip it (dp[i-1][c]) or take it if w[i] <= c (dp[i-1][c-w[i]] + v[i]). The recurrence is: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) when w[i] <= c, otherwise dp[i][c] = dp[i-1][c]. Base case: dp[0][c] = 0 for all c.
2D DP Table Implementation
The 2D table has (n+1) x (W+1) entries and fills row by row for each item. After filling all rows, dp[n][W] holds the maximum value. This runs in O(n × W) time and O(n × W) space — a pseudo-polynomial complexity that is efficient when W is small.
def knapsack_2d(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c] # skip item i
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8)) # 10Why Iterate Capacity in Reverse for 1D DP
The key observation: row i only depends on row i-1. So we can use a single 1D array and update it in-place. However, if we iterate capacity c from left to right (small to large), item i might be counted twice — we could use the updated value for c-w[i] that already includes item i. Iterating right to left (large to small) ensures each item is used at most once per row update.
# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] may already use item i
# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] still from previous row1D Space-Optimised Implementation
By keeping only one array and iterating capacity from W down to w[i], we achieve the same result as the 2D table in O(W) space. The time complexity remains O(n × W). This space optimisation is critical to memorise — interviewers frequently ask you to reduce the 2D knapsack to 1D.
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(W, w - 1, -1): # iterate RIGHT TO LEFT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8)) # 10Reconstructing the Selected Items
To find which items were selected, you need the full 2D table. After filling it, start at dp[n][W] and trace backwards: if dp[i][c] != dp[i-1][c], item i was included — subtract its weight from c and move to row i-1. Continue until i = 0. The 1D optimisation discards this reconstruction capability.
def knapsack_with_items(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c]
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
# Reconstruct
selected, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i-1][c]:
selected.append(i-1)
c -= weights[i-1]
return dp[n][W], selected[::-1]
print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))Practical Example: Maximize Total Value
Consider items: weights=[2,3,4,5], values=[3,4,5,6], W=8. Optimal: take items with weight 3 (value 4) and weight 5 (value 6) — total weight 8, value 10. Or take weight 2 and 5 — total value 9. Or weight 2 and 3 — value 7. The DP correctly finds the maximum 10. Notice that the greedy approach (take highest value-to-weight ratio) would take item of ratio 1.5 first (weight 2, value 3) — not always optimal.
Fractional Knapsack vs 0/1 Knapsack
In Fractional Knapsack, you can take fractions of items. This is solvable greedily by sorting on value/weight ratio. In 0/1 Knapsack, items are indivisible — greedy fails, DP is required. Interviewers use this distinction to test whether you know when greedy is applicable. If asked about the fractional variant, immediately mention greedy with sorting; if 0/1, reach for DP.
# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total = 0
for v, w in items:
if W >= w:
total += v; W -= w
else:
total += v * (W / w); break
return total
print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))Pseudo-Polynomial Time Complexity
0/1 Knapsack is NP-complete, yet we solve it in O(nW) time. The contradiction resolves because O(nW) is pseudo-polynomial: W is a value, not the input size. The binary representation of W takes O(log W) bits, so the true complexity is O(n × 2^(log W)) which is exponential in the input size. When W is small (e.g., 10⁴), the DP is practical; when W can be 10⁹, we need different approaches.
Interviewer Follow-Up: Large Capacity
If the interviewer constrains W to be very large (e.g., 10⁹) but n is small, the standard DP breaks. Alternatives include: (1) meet-in-the-middle in O(2^(n/2) × n) time, (2) greedy approximation for fractional variant, or (3) branch-and-bound. For most interview problems with W <= 10⁵, the 1D DP with backward iteration is the expected answer.
Meet-in-the-Middle for Large Capacity
When W is very large but n is small (e.g., n=40), the standard O(nW) DP is infeasible but brute-force 2^n is too slow. Meet-in-the-middle splits items into two halves, enumerates all 2^(n/2) subsets for each half, and pairs them optimally. Sort one half by weight, then for each subset of the other half use binary search to find the best pairing within capacity. This runs in O(2^(n/2) × n) — practical for n up to 40.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: 0/1 knapsack DP has state dp[i][c] representing max value with i items and capacity c, the recurrence chooses to skip or take each item, and the 1D space optimisation iterates capacity right to left to prevent double-counting items. Next up we explore unbounded knapsack where items can be reused, and apply it to Coin Change II.
Frequently asked questions
Is the “0/1 Knapsack and Space Optimisation” lesson free?
Yes — the full text of “0/1 Knapsack and Space Optimisation” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “0/1 Knapsack and Space Optimisation”?
Derive the 0/1 knapsack recurrence, fill the 2D table, then reduce to a 1D array by iterating capacity in reverse. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “0/1 Knapsack and Space Optimisation” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- 0/1 Knapsack and Space Optimisation
- Unbounded Knapsack and Coin Change II
- Partition Equal Subset Sum
- Target Sum with Positive and Negative Signs