0/1 Knapsack

#Problem Statement

Given n items with weights weights[i] and values values[i], and a knapsack with capacity W, determine the maximum value that can be put in the knapsack. Each item can be used at most once.

Input:  weights = [1, 3, 4, 5], values = [1, 4, 5, 7], W = 7
Output: 9  (items with weight 3 and 4: value 4+5=9)

#State Definition

dp[i][j] = maximum value using the first i items with capacity j.

For each item i, two choices:

• Exclude item i: dp[i][j] = dp[i-1][j] (best without this item)
• Include item i (if weights[i-1] <= j): dp[i][j] = values[i-1] + dp[i-1][j - weights[i-1]]

dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j - weights[i-1]])

Base cases: dp[0][*] = 0 (no items = 0 value), dp[*][0] = 0 (0 capacity = 0 value).

#2D DP — O(n·W) time, O(n·W) space

public int knapsack(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[][] dp = new int[n + 1][W + 1];
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j]; // exclude item i
            if (weights[i-1] <= j) {
                dp[i][j] = Math.max(dp[i][j],
                    values[i-1] + dp[i-1][j - weights[i-1]]); // include item i
            }
        }
    }
    return dp[n][W];
}

#1D Space Optimization — O(W) space ✅

Since dp[i][j] only depends on row i-1, collapse to a single 1D array. Traverse j from right to left to prevent using the same item twice.

public int knapsack(int[] weights, int[] values, int W) {
    int[] dp = new int[W + 1];
 
    for (int i = 0; i < weights.length; i++) {
        // Traverse right-to-left: prevents item i from being used twice
        for (int j = W; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], values[i] + dp[j - weights[i]]);
        }
    }
    return dp[W];
}

Why right-to-left? In the 2D table, dp[i][j] uses dp[i-1][j - w] — the previous row's value. If you traverse left-to-right with a 1D array, dp[j-w] may already be updated with the current item, allowing it to be used multiple times (that would be the unbounded knapsack). Right-to-left ensures dp[j-w] still refers to the previous item's state.

#Tracing the Example

weights=[1,3,4,5], values=[1,4,5,7], W=7

After processing each item (1D array, right-to-left):

Return dp[7] = 9 ✓

#0/1 vs Unbounded Knapsack

#Complexity

#Key Insight

0/1 Knapsack is the include/exclude DP template. The decision at each item is binary — take it or leave it. The "0/1" in the name means each item has a binary choice.

This structure generalizes to many LeetCode problems where this exact connection isn't obvious:

#Edge Cases

• Item weight > capacity: that item can never be included. The right-to-left loop stops at j >= weights[i], naturally skipping it.
• All items too heavy: dp stays all 0, return 0.
• W = 0: return 0. Inner loop condition j >= weights[i] is never satisfied.