Chapter 55

Home

Refactoring: 1D Knapsack

The 2D knapsack table is N+1 rows × W+1 columns — O(N×W) memory. But each row only depends on the previous row. By iterating capacity backwards, we can overwrite in place and reduce to a single 1D array of size W+1.

Before: 2D Table (O(N×W) memory)

C++ — O(N×W) memory

vector> dp(n + 1, vector(W + 1, 0));

for (int i = 1; i <= n; i++)
    for (int c = 0; c <= W; c++) {
        dp[i][c] = dp[i - 1][c];
        if (c >= w[i - 1])
            dp[i][c] = max(dp[i][c], v[i - 1] + dp[i - 1][c - w[i - 1]]);
    }

// Memory: (n+1) × (W+1) × sizeof(int)
// n=2000, W=2000:  ~16 MB

🚨 Memory scales with N×W

For N = 2000 and W = 2000, a 2D DP array is ~16 MB. Fine for most contests, but some problems push N = 10⁵ with W = 10⁵ — impossible with 2D.

After: 1D Array (O(W) memory)

The key insight: dp[i][c] only reads from dp[i-1][*]. If we iterate capacity backwards (from W down to 0), we never overwrite a value that will be read later in the same item's loop.

C++ — O(W) memory, backward iteration

int knapsack_1d(vector& w, vector& v, int W) {
    vector dp(W + 1, 0);

    for (int i = 0; i < n; i++)
        // ← CRITICAL: iterate capacity BACKWARDS
        for (int c = W; c >= w[i]; c--)
            dp[c] = max(dp[c], v[i] + dp[c - w[i]]);

    return dp[W];
}

// Memory: (W+1) × sizeof(int) = ~8 KB for W=2000

Rust — O(W) memory

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

    for i in 0..weights.len() {
        for c in (weights[i]..=w).rev() {  // ← backwards
            dp[c] = dp[c].max(values[i] + dp[c - weights[i]]);
        }
    }
    dp[w]
}

💡 Why backwards?

Forward iteration (c = 0..W) would mean dp[c - w[i]] might have already been updated for the current item i — effectively allowing unlimited uses of the same item (unbounded knapsack). Backward ensures we read the previous item's values, not the current one's. This is the difference between 0/1 and unbounded knapsack.

Key Takeaways

Practice