0/1 Knapsack and Space Optimisation

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.

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.