背包问题：0/1 背包、完全背包与变体

背包问题概述

背包问题是 DP 中一类经典模型，核心是"在约束条件下，做选择使目标最优"。

0/1 背包

状态：dp[j] = 容量为 j 时的最大价值
关键：j 从大到小遍历，防止同一物品被选多次

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--) {  // 从右往左！
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

分割等和子集（LeetCode 416）

判断数组能否被分成两个和相等的子集。

等价于：能否在数组中选若干元素，使其和恰好等于 sum/2（0/1 背包求可行性）。

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--) {  // 从右往左
            dp[j] = dp[j] || dp[j - n];
        }
    }
    return dp[target];
}

完全背包

每种物品可以选无限次，j 从小到大遍历（允许重复使用）：

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++) {  // 从左往右！
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

零钱兑换（LeetCode 322）：最少硬币数

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // 初始化为大值（不可达）
    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];
}

零钱兑换 II（LeetCode 518）：组合数

求方案数时，含义略有不同：dp[j] = 凑成金额 j 的组合数。

int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;  // 凑成 0 的方案数为 1（都不选）
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] += dp[j - coin];
        }
    }
    return dp[amount];
}

排列数 vs 组合数：上面的写法（先遍历物品，后遍历容量）得到的是组合数（物品顺序无关）。
若先遍历容量，后遍历物品，得到的是排列数（顺序有关，如爬楼梯）。

0/1 vs 完全背包：关键对比

综合练习

目标和（LeetCode 494）

将 +/- 分配给每个数，使表达式结果等于 target。

用数学转换：设加号集合和为 P，减号集合和为 N，则 P - N = target 且 P + N = sum，得 P = (sum + target) / 2。

转化为 0/1 背包求方案数（选若干元素和恰好为 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--) {  // 0/1 背包，从右往左
            dp[j] += dp[j - n];
        }
    }
    return dp[p];
}