0/1 Knapsack Visualization for Coding Interviews
DP table by item × capacity; traceback picks selected items.
Concept
The 0/1 Knapsack problem is the textbook example of pseudopolynomial dynamic programming and a recurring interview favorite because it sits at the boundary of 'easy to state, hard to solve optimally'. You are given n items, each with a weight and a value, and a sack with capacity W; pick a subset that maximizes total value without exceeding W, taking each item at most once. Real-world analogues include cargo loading, resource allocation under a budget, CPU scheduling with deadlines, and feature selection with a latency budget. The canonical DP runs in O(nW) time and space where W is the capacity — polynomial in the value of W but exponential in its bit length, which is why knapsack is NP-hard in the general sense. For tiny W the DP is fast; for huge W you fall back to branch-and-bound, FPTAS approximations, or ILP.
How it works
Define dp[i][w] as the maximum value achievable using the first i items with weight budget w. For each item i with weight wi and value vi, we have two choices: skip it, giving dp[i-1][w], or take it (if wi <= w), giving dp[i-1][w - wi] + vi. The recurrence is dp[i][w] = max(dp[i-1][w], dp[i-1][w - wi] + vi) where the second term is only considered when wi <= w. The base row dp[0][w] = 0 represents no items picked. The answer is dp[n][W]. To reconstruct which items were chosen, walk the table backwards from dp[n][W]: if dp[i][w] != dp[i-1][w], item i was taken, so record it and move to dp[i-1][w - wi]; otherwise move to dp[i-1][w]. A classic space optimization collapses the 2D table to a 1D array indexed by w, iterated in descending order of w to avoid reusing an item within the same iteration — this is the 'why descending' puzzle that catches interviewees. Unbounded knapsack (each item usable many times) uses the same 1D trick but iterates w in ascending order.
Implementation
public final class Knapsack01 {
public static final class Result {
public final int maxValue;
public final boolean[] pick;
public Result(int maxValue, boolean[] pick) { this.maxValue = maxValue; this.pick = pick; }
}
private Knapsack01() {}
public static Result knapsack01(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
int wi = weights[i - 1], vi = values[i - 1];
for (int w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w];
if (wi <= w) {
int take = dp[i - 1][w - wi] + vi;
if (take > dp[i][w]) dp[i][w] = take;
}
}
}
boolean[] pick = new boolean[n];
int w = capacity;
for (int i = n; i > 0 && w >= 0; i--) {
if (dp[i][w] != dp[i - 1][w]) {
pick[i - 1] = true;
w -= weights[i - 1];
}
}
return new Result(dp[n][capacity], pick);
}
public static int knapsack01Rolling(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
int wi = weights[i], vi = values[i];
for (int w = capacity; w >= wi; w--) {
int take = dp[w - wi] + vi;
if (take > dp[w]) dp[w] = take;
}
}
return dp[capacity];
}
}
Complexity
- Time:
O(n * W) - Space (full):
O(n * W) - Space (rolling):
O(W) - Class:
Pseudopolynomial / NP-hard
Common pitfalls
- Iterating w ascending in the 1D version — that turns 0/1 into unbounded knapsack silently.
- Letting W be 'the number' when it is actually large (e.g., 10^9) — the DP blows up; use branch-and-bound.
- Forgetting that the 2D table base case dp[0][w] = 0 is automatic in Java but not in C.
- Reconstructing picks by comparing values instead of the source of the max — breaks on ties.
- Mixing fractional knapsack's greedy-by-ratio with 0/1 — fractional is a different problem.
Key design decisions & trade-offs
- 2D vs 1D DP — Chosen: 1D when picks not needed. Halves memory; loses ability to reconstruct selected items without extra work.
- Exact DP vs approximation — Chosen: FPTAS for large W. Scale down values to get an (1 - epsilon) approximation in polynomial time.
- DP vs branch-and-bound — Chosen: B&B when n is small and W huge. DP is pseudopolynomial; B&B with good pruning can handle W = 10^12.
Practice problems
Interview follow-ups
- Solve unbounded knapsack by iterating w ascending in the 1D DP.
- Extend to bounded knapsack where item i can be taken up to k_i times.
- Implement a fractional knapsack greedy by value/weight ratio for comparison.
- Add a 'meet in the middle' solver for n up to 40 and huge W.
Why it matters
0/1 Knapsack is a core part of the Dynamic Programming toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".