Knapsack Problems: 0/1, Complete, and Variants

Overview

Knapsack problems are a classic DP paradigm focusing on "making choices under constraints to optimize a goal."

0/1 Knapsack

State: dp[j] = maximum value with capacity $j$. Key: The inner capacity loop must iterate backwards (from $W$ down to $weight$) to ensure each item is processed as a "new selection" relative only to previous items, not itself.

int knapsack01(int[] weights, int[] values, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int j = W; j >= weights[i]; j--) { // REVERSED loop!
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

Partition Equal Subset Sum (LeetCode 416)

Can we partition an array into two subsets with equal sums?

Reduction: Can we select items that sum exactly to totalSum / 2? (0/1 Knapsack for feasibility).

boolean canPartition(int[] nums) {
    int sum = 0;
    for (int n : nums) sum += n;
    if (sum % 2 != 0) return false;
    
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int n : nums) {
        for (int j = target; j >= n; j--) { // Backward
            dp[j] = dp[j] || dp[j - n];
        }
    }
    return dp[target];
}

Complete Knapsack

Items can be chosen an unlimited number of times. The inner loop must iterate forwards (from $weight$ up to $W$) so that updates to dp[j] can build upon earlier selections of the same item.

int knapsackComplete(int[] weights, int[] values, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int j = weights[i]; j <= W; j++) { // FORWARD loop!
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

Coin Change (LeetCode 322): Minimum Count

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // Max value (unreachable)
    dp[0] = 0;
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Coin Change II (LeetCode 518): Number of Ways

State: dp[j] = number of combinations to make sum $j$.

int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1; // One way to make 0: pick nothing
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] += dp[j - coin];
        }
    }
    return dp[amount];
}

Combinations vs. Permutations:

• If items are the outer loop (as above), you are counting combinations (order of picking coins doesn't matter).
• If capacity is the outer loop, you are counting permutations (picking 1,2 is different from 2,1).

0/1 vs. Complete: At a Glance

Target Sum (LeetCode 494)

The problem asks to reach a target sum by assigning $+/-$ to each array element. Total sum is $S$. Let $P$ be the sum of positive-signed numbers and $N$ be the sum of negative-signed numbers:

• $P - N = target$
• $P + N = sum(nums)$
• Adding these: $2P = target + sum(nums) \implies P = (target + sum(nums)) / 2$

The problem reduces to a 0/1 Knapsack finding total ways to reach sum $P$.

int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int n : nums) sum += n;
    if ((sum + target) % 2 != 0 || Math.abs(target) > sum) return 0;
    
    int p = (sum + target) / 2;
    int[] dp = new int[p + 1];
    dp[0] = 1;
    for (int n : nums) {
        for (int j = p; j >= n; j--) {
            dp[j] += dp[j - n];
        }
    }
    return dp[p];
}

筋