0/1 Knapsack: Dynamic Programming & Space Optimization

The 0/1 Knapsack problem is the canonical foundation of dynamic programming. Given N items—each with a weight w[i] and value v[i]—and a bag of maximum capacity W, what combination of items maximizes total value without exceeding capacity?

The name 0/1 signifies that every item is discrete: you either take the entire item (1) or leave it behind (0). No fractions or multiples are permitted.

The Decision State & Recurrence Relation

A brute-force recursion explores every subset of items, taking exponential O(2^N) time. But notice that for any item i and remaining capacity w, the optimal value depends purely on subproblems already solved:

flowchart TD
    State["Evaluating Item i (weight = w_i, val = v_i)\nat Capacity w"] --> Check{"Can Item Fit?\n(w >= w_i)"}
    Check -->|No| ExcludeOnly["Must Exclude Item:\ndp[i][w] = dp[i-1][w]"]
    Check -->|Yes| Choices{"Evaluate Both Choices"}
    Choices --> OptionA["Exclude Item i:\ndp[i-1][w]"]
    Choices --> OptionB["Include Item i:\nv_i + dp[i-1][w - w_i]"]
    OptionA --> MaxResult["Optimal Value:\nmax(Option A, Option B)"]
    OptionB --> MaxResult

The Formal Recurrence

Let dp[i][w] represent the maximum value achievable using a subset of the first i items with a weight budget of w:

• If w < weights[i-1]: dp[i][w] = dp[i-1][w] (Item is too heavy to fit)
• If w ≥ weights[i-1]: dp[i][w] = Math.max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])

Standard 2D Tabulation Implementation

Java Implementation

public class Knapsack01 {
    public static int knapsack2D(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++) {
            int currentWeight = weights[i - 1];
            int currentValue = values[i - 1];

            for (int w = 1; w <= capacity; w++) {
                if (currentWeight <= w) {
                    dp[i][w] = Math.max(
                        dp[i - 1][w],                                  // Exclude
                        currentValue + dp[i - 1][w - currentWeight]   // Include
                    );
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][capacity];
    }
}

The 1D Array Space Optimization (Why Backward Iteration Matters)

In the 2D table, computing row i depends only on values from the previous row i - 1. You never look back to rows i - 2 or earlier. Therefore, the entire 2D matrix can be compressed into a single 1D array of size capacity + 1.

The Golden Invariant: When updating the 1D array, you must iterate capacity w backwards from capacity down to weights[i]. If you iterated forward, dp[w - weight] would already reflect the current item, effectively allowing an item to be picked multiple times (which converts 0/1 knapsack into unbounded knapsack!).

Python Implementation (1D Optimized)

def knapsack_1d(weights: list[int], values: list[int], capacity: int) -> int:
    """Computes optimal 0/1 knapsack value in O(N * W) time and O(W) space."""
    dp = [0] * (capacity + 1)

    for weight, value in zip(weights, values):
        # Iterate backwards to avoid using the same item twice
        for w in range(capacity, weight - 1, -1):
            dp[w] = max(dp[w], value + dp[w - weight])

    return dp[capacity]

# Example execution
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
max_cap = 5
print(knapsack_1d(weights, values, max_cap)) # Output: 7 (items 1 and 2: wt 2+3, val 3+4)

TypeScript Implementation

export function knapsackOptimized(
  weights: number[],
  values: number[],
  capacity: number
): number {
  const dp: number[] = new Array(capacity + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    const w = weights[i];
    const v = values[i];

    for (let cap = capacity; cap >= w; cap--) {
      dp[cap] = Math.max(dp[cap], v + dp[cap - w]);
    }
  }

  return dp[capacity];
}

Common Problem Reductions

Many interview and engineering problems look unrelated to knapsack at first glance, but reduce directly to this pattern:

• Subset Sum Problem: Can a subset of numbers sum to target S? → Set values[i] = weights[i] = nums[i] and check if dp[S] == S.
• Equal Partition: Can an array be partitioned into two subsets of equal sum? → If total sum is odd, return false; otherwise solve Subset Sum for target = sum / 2.
• Target Sum (± signs): Assigning + or - to reach target T → Partitions array into positive set P and negative set N. Since P - N = T and P + N = Sum, 2P = T + Sum ⇒ P = (T + Sum) / 2. Solve 0/1 Knapsack for capacity P.

Complexity & Space Trade-offs