Intermediate LevelData Structures & Algorithms
How do you solve the 0/1 Knapsack problem with Dynamic Programming?
ā Interview Prompt: Solve the 0/1 Knapsack problem using 2D and space-optimised 1D DP, explaining why items must be processed in reverse order.
Problem: Given $N$ items each with weight $w_i$ and value $v_i$, maximise value without exceeding capacity $W$. Each item can be taken 0 or 1 times.
DP State:
dp[i][c] = max value using items $[0..i-1]$ with capacity $c$.
```
dp[i][c] = max(dp[i-1][c], // skip item i
dp[i-1][c - w[i]] + v[i]) // take item i (if w[i] <= c)
```
1D Space Optimisation:
Iterate capacity right-to-left to prevent reusing the same item (0/1 constraint). Left-to-right would give unbounded knapsack.
Code Implementation Example
typescript
function knapsack(weights: number[], values: number[], W: number): number {
const n = weights.length;
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < n; i++) {
// Traverse BACKWARDS ā prevents reusing item i (0/1 constraint)
for (let c = W; c >= weights[i]; c--) {
dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
}
}
return dp[W];
}
console.log(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 5)); // 7 (items 0+1)š”0/1 Knapsack with O(W) space ā reverse traversal prevents item reuse.
šÆ Interview Key Takeaway
Reverse capacity traversal in 1D Knapsack enforces the 0/1 constraint. Forward traversal (unbounded knapsack) allows infinite reuse of items.
#DSA#Knapsack#Dynamic Programming#0-1 Knapsack#Intermediate
Back to all Data Structures & Algorithms Questionsā