0/1 Knapsack Problem

Given N items, each with weight wᵢ and value vᵢ, and a knapsack of capacity W, choose a subset to maximise total value. Each item is take or leave (0/1) — no fractions. This is the classic DP problem, the gateway to 2D tabulation.

The Recurrence

For each item i and each capacity c, you have two choices:

Exclude item i

Best value with items 1..i−1 at capacity c: dp[i-1][c]

Include item i (if it fits)

Value of item i + best with items 1..i−1 at capacity c−wᵢ: vᵢ + dp[i-1][c-wᵢ]

C++ — 0/1 Knapsack (2D)

int knapsack(vector& weights, vector& values, int W) {
    int n = weights.size();
    vector> dp(n + 1, vector(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            // Exclude item i
            dp[i][c] = dp[i - 1][c];
            // Include item i (if it fits)
            if (c >= weights[i - 1])
                dp[i][c] = max(dp[i][c],
                    values[i - 1] + dp[i - 1][c - weights[i - 1]]);
        }
    }
    return dp[n][W];
}

Rust — 0/1 Knapsack (2D)

fn knapsack(weights: &[usize], values: &[i32], w: usize) -> i32 {
    let n = weights.len();
    let mut dp = vec![vec![0; w + 1]; n + 1];

    for i in 1..=n {
        for c in 0..=w {
            dp[i][c] = dp[i - 1][c];  // exclude
            if c >= weights[i - 1] {
                dp[i][c] = dp[i][c].max(
                    values[i - 1] + dp[i - 1][c - weights[i - 1]]);
            }
        }
    }
    dp[n][w]
}

Key Takeaways

→ 0/1 Knapsack: 2D DP where dp[i][c] = max value using first i items, capacity c.
→ Recurrence: dp[i][c] = max(dp[i-1][c], vᵢ + dp[i-1][c - wᵢ]).
→ O(N×W) time, O(N×W) memory — can be reduced to O(W) (next chapter).

The Recurrence

C++ — 0/1 Knapsack (2D)

Rust — 0/1 Knapsack (2D)

Key Takeaways

Practice