0 1 Knapsack
The 0/1 knapsack problem is one of the foundational problems in combinatorial optimization. Given n items, each with a weight w[i] and a value v[i], and a ...
Problem Statement and DP Formulation
The 0/1 knapsack problem is one of the foundational problems in combinatorial optimization. Given n items, each with a weight w[i] and a value v[i], and a knapsack with maximum capacity W, determine the maximum total value you can carry. Each item can be taken at most once (hence "0/1" — you either take it or you do not). Fractions are not allowed.
Define dp[i][w] as the maximum value achievable using items 1 through i with a weight limit of w. Base cases: dp[0][w] = 0 for all w (no items available), and dp[i][0] = 0 for all i (no capacity). Recurrence: if w[i] > w, you cannot include item i, so dp[i][w] = dp[i-1][w]. Otherwise, dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i]).
A worked example: W = 6, items with (weight, value) — (2, 6), (2, 10), (3, 12). Fill the 4x7 table row by row. dp[1][2] = 6 (take item 1), dp[1][4] = 6, dp[1][6] = 6. dp[2][2] = 10 (take item 2), dp[2][4] = 16 (take both), dp[2][6] = 16. dp[3][3] = 12, dp[3][5] = 22 (items 2+3), dp[3][6] = 22. Maximum value is 22.
Time complexity: O(n * W). Space complexity: O(n * W) for the full table, reducible to O(W) with a rolling array. Importantly, this is pseudo-polynomial time — it is polynomial in the numeric value of W but exponential in the number of bits needed to represent W.
Interview tip: When an interviewer asks why the knapsack solution is not considered a polynomial algorithm, explain pseudo-polynomial time. The algorithm's complexity depends on the numeric value of W, which can be exponentially large relative to the number of bits needed to encode W. This is a key theoretical distinction.
Space Optimization to O(W)
The full O(n * W) DP table for 0/1 knapsack can be reduced to O(W) by observing that row i depends only on row i-1. Use a single 1D array dp[0..W] representing the previous row, and update it in place — but critically, iterate w from W down to w[i] to avoid using item i more than once.
Why iterate backwards? When computing dp[w] = max(dp[w], dp[w - w[i]] + v[i]), the term dp[w - w[i]] must refer to the state before item i was considered (the previous row). If you iterate w from left to right, dp[w - w[i]] may already be updated to include item i, effectively allowing it to be taken multiple times. Iterating right to left ensures dp[w - w[i]] has not yet been updated in this pass.
Contrast with unbounded knapsack, where each item can be taken any number of times. For unbounded knapsack, iterate w from w[i] to W. The forward direction deliberately allows dp[w - w[i]] to reflect already-included copies of item i.
Pseudocode for 0/1 knapsack with O(W) space: initialize dp[0..W] = 0. For each item i from 1 to n: for w from W down to w[i]: dp[w] = max(dp[w], dp[w - w[i]] + v[i]). Return dp[W].
Reconstruction is not directly possible with a single array because the choice information (which items were selected at each capacity) is overwritten. To reconstruct items, you either keep the full table or use a backtracking technique that re-runs item decisions from the optimal value.
Interview tip: Drawing two rows of the table and showing that row i reads from row i-1, then demonstrating that reverse iteration preserves this property, is far more convincing than just asserting that you should "iterate backwards." Visual explanation of the direction matters enormously for clarity.
Variants: Subset Sum, Equal Partition, and Bounded Knapsack
The 0/1 knapsack framework underlies several important variants. The subset sum problem asks: does a subset of a given array sum to exactly a target T? This is a special case of 0/1 knapsack where all item values equal their weights and you want to know if dp[n][T] > 0 (or equal to T). The DP table is boolean: dp[i][s] = true if some subset of items 1..i sums to s.
The partition equal subset sum problem asks: can the array be split into two subsets with equal sum? If the total sum is odd, the answer is immediately false. If even, check whether a subset sums to total_sum / 2 using the subset sum DP. This is a popular Leetcode problem and appears frequently in interviews.
Count of subsets with a given sum asks not whether a subset exists, but how many such subsets exist. Change the DP to count: dp[i][s] = dp[i-1][s] + dp[i-1][s - w[i]]. The recurrence adds counts instead of taking max.
The bounded knapsack problem allows each item to be taken at most k[i] times. A naive approach treats each item as k[i] separate 0/1 items, giving O(sum(k[i]) * W) time. A smarter approach uses binary representation: split k[i] copies into groups of 1, 2, 4, ..., and a remainder. This converts bounded into 0/1 with O(log(k[i])) items per original item, giving O(n * log(max_k) * W) time.
Interview tip: When you recognize a problem as partition-equal-subset-sum, connect it explicitly to 0/1 knapsack. Saying "this is knapsack with target T = total_sum / 2" instantly shows pattern recognition and saves time over re-deriving the DP from scratch in an interview.