Q18: How do you solve the 0/1 Knapsack Problem using Dynamic Programming?
Given $n$ items with weights $w[i]$ and values $v[i]$, maximize total value in knapsack capacity $W$. State $dp[i][w]$ represents maximum value using first $i$ items with capacity $w$. Recurrence: if $w[i-1] le w$, $dp[i][w] = max(v[i-1] + dp[i-1][w - w[i-1]], dp[i-1][w])$.
0/1 Knapsack 1D Array Optimization
public class Knapsack {
public static int knapsack(int W, int[] wt, int[] val, int n) {
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) {
for (int w = W; w >= wt[i]; w--) { // Reverse iteration
dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
}
}
return dp[W];
}
}💡 Iterates backwards over capacity $W$ to update knapsack state in 1D array space.
Key Takeaways
- 2D DP table size: $(N+1) imes (W+1)$.
- Can be optimized to a 1D DP array of size $W+1$ by traversing backwards.
Knowledge Check
Why MUST the inner loop iterate BACKWARDS from W down to wt[i] in the 1D array DP space optimization?