0/1 Knapsack Problem

Pattern: Dynamic Programming - 0/1 Knapsack
Difficulty: Medium
Key Concept: “Pick or Don’t Pick” binary choice for each element

Problem Statement

You are given n items with weights and values. You have a backpack with capacity W. Maximize the total value without exceeding the weight limit. Each item can only be used once.

---

The Scenario

You are a thief with a backpack that holds 4kg. You see three items:

1. Item A: Value $150, Weight 3kg
2. Item B: Value $100, Weight 2kg
3. Item C: Value $200, Weight 4kg

You can’t take half an item (0/1 = take it or leave it).

---

Brute Force: Recursive - O(2^n)

public class Knapsack {
    public static int solve(int[] weights, int[] values, int capacity) {
        return helper(weights, values, capacity, 0);
    }

    private static int helper(int[] wt, int[] val, int cap, int idx) {
        if (idx == wt.length || cap == 0) return 0;

        int exclude = helper(wt, val, cap, idx + 1);

        int include = 0;
        if (wt[idx] <= cap) {
            include = val[idx] + helper(wt, val, cap - wt[idx], idx + 1);
        }

        return Math.max(include, exclude);
    }
}

---

Memoized (Top-Down) - O(n * W)

public class Knapsack {
    public static int solve(int[] weights, int[] values, int capacity) {
        int[][] memo = new int[weights.length][capacity + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return helper(weights, values, capacity, 0, memo);
    }

    private static int helper(int[] wt, int[] val, int cap, int idx, int[][] memo) {
        if (idx == wt.length || cap == 0) return 0;
        if (memo[idx][cap] != -1) return memo[idx][cap];

        int exclude = helper(wt, val, cap, idx + 1, memo);

        int include = 0;
        if (wt[idx] <= cap) {
            include = val[idx] + helper(wt, val, cap - wt[idx], idx + 1, memo);
        }

        memo[idx][cap] = Math.max(include, exclude);
        return memo[idx][cap];
    }
}

---

Tabulated (Bottom-Up) - O(n * W) time, O(n * W) space

public class Knapsack {
    public static int solve(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                dp[i][w] = dp[i - 1][w];

                if (weights[i - 1] <= w) {
                    int include = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                    dp[i][w] = Math.max(dp[i][w], include);
                }
            }
        }

        return dp[n][capacity];
    }
}

---

DP Table Trace

weights = [3, 2, 4], values = [150, 100, 200], capacity = 4

          Cap →  0    1    2    3    4
Items ↓
0 (none)         0    0    0    0    0
A (3kg,$150)     0    0    0  150  150
B (2kg,$100)     0    0  100  150  250
C (4kg,$200)     0    0  100  150  250

Answer: $250 (take A + B = 3kg + 2kg = 5kg? No - A=3kg+B=2kg=5kg > 4kg)
Correction: dp[2][4] = max(dp[1][4], 100 + dp[1][2]) = max(150, 100+0) = 150
Actually with optimal: take B at 2kg ($100) leaves 2kg → no item fits remaining.
Take A at 3kg ($150) leaves 1kg → nothing fits. So best = $150 or $200 (item C alone).

Final answer = $200 (just item C at 4kg)

---

The Universal DP Formula

$$DP[i][w] = \max(DP[i-1][w], ; val[i] + DP[i-1][w - wt[i]])$$

• DP[i-1][w] = result if we ignore current item
• val[i] + DP[i-1][w - wt[i]] = result if we include current item

---

Complexity

Approach	Time	Space
Recursive	O(2^n)	O(n)
Memoized	O(n * W)	O(n * W)
Tabulated	O(n * W)	O(n * W)
Space-Opt	O(n * W)	O(W)