2️⃣ 0/1 Knapsack Problem

🟡 IntermediateDP Pattern: 2D Grid

📋 Problem Statement

Given N items each with weight w[i] and value v[i], and a knapsack of capacity W. Each item can be taken at most once (0 or 1). Maximize total value without exceeding capacity.

💻 Solution: Bottom-Up DP

function knapsack01(array $weights, array $values, int $capacity): int {
    $n = count($weights);
    // dp[i][w] = max value using first i items, capacity w
    $dp = array_fill(0, $n+1, array_fill(0, $capacity+1, 0));

    for ($i = 1; $i <= $n; $i++) {
        for ($w = 0; $w <= $capacity; $w++) {
            if ($weights[$i-1] <= $w) {
                $dp[$i][$w] = max(
                    $dp[$i-1][$w],                          // Skip
                    $dp[$i-1][$w-$weights[$i-1]] + $values[$i-1] // Take
                );
            } else {
                $dp[$i][$w] = $dp[$i-1][$w]; // Can't take
            }
        }
    }
    return $dp[$n][$capacity];
}

// Space-optimized: O(W) space
function knapsack01Optimized(array $weights, array $values, int $capacity): int {
    $n = count($weights);
    $dp = array_fill(0, $capacity+1, 0);

    for ($i = 0; $i < $n; $i++) {
        // Go backwards to avoid reusing item
        for ($w = $capacity; $w >= $weights[$i]; $w--) {
            $dp[$w] = max($dp[$w], $dp[$w - $weights[$i]] + $values[$i]);
        }
    }
    return $dp[$capacity];
}

$w = [2,3,4,5]; $v = [3,4,5,6];
echo knapsack01($w, $v, 8); // 10
echo knapsack01Optimized($w, $v, 8); // 10

📝 DP Table Dry Run

Items: (w=2,v=3), (w=3,v=4), (w=4,v=5), (w=5,v=6) | Capacity: 8

i\w 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 (w=2) 0 0 3 3 3 3 3 3 3
2 (w=3) 0 0 3 4 4 7 7 7 7
3 (w=4) 0 0 3 4 5 7 8 9 9
4 (w=5) 0 0 3 4 5 7 8 9 10

Answer: 10 (items with w=3,v=4 + w=5,v=6 → total w=8, v=10)

📊 Complexity

Naive Recursion O(2ⁿ)
DP (2D) O(n*W) time, O(n*W) space
DP (1D optimized) O(n*W) time, O(W) space ⭐

Note: O(n*W) is pseudo-polynomial — it depends on W's numeric value, not input size.

Previous: Fibonacci Next: Coin Change