背包问题：01 背包与完全背包

背包问题是动规的地基，后面一大票"看起来和背包毫无关系"的题目（分割子集、凑硬币、单词拆分），剥掉题面后内核都是背包。本文聚焦两个最基础的模型：01 背包（每件物品最多拿一次）和完全背包（每件物品可以拿无限次），重点讲清楚那个最容易忘的细节——遍历顺序。

一、01 背包：问题描述

有 n 件物品和一个容量为 W 的背包。第 i 件物品重量 weight[i]、价值 value[i]，每件只能选一次。求装入背包的物品最大价值总和。

先看暴力思路：每件物品都有"选"和"不选"两种状态，枚举所有组合是 O(2^n)，n 稍大就爆炸。背包的两个选择恰好构成递推结构，这正是 DP 的主场。

二、二维 dp 解法

按五部曲走：

状态定义：dp[i][j] 表示"考虑第 0..i 件物品、背包容量为 j 时的最大价值"。
递推公式：对第 i 件物品只有两种决策——
- 不放它：dp[i][j] = dp[i-1][j]，容量不变；
- 放它（前提 j >= weight[i]）：腾出 weight[i] 的空间，dp[i][j] = dp[i-1][j - weight[i]] + value[i]。
两者取较大值。
初始化：第一行 dp[0][j] 表示只考虑第 0 件物品，容量够就放：j >= weight[0] 时为 value[0]，否则为 0；第一列容量为 0 恒为 0。
遍历顺序：先物品后容量（反过来也可以，二维下两者等价）。
验证：画 3 件物品的表手动填一遍。

public int knapsack01(int[] weight, int[] value, int W) {
    int n = weight.length;
    // dp[i][j]: 前 i 件物品（下标 0..i-1）、容量 j 下的最大价值
    int[][] dp = new int[n][W + 1];
    // 初始化第一行：只放第 0 件物品
    for (int j = weight[0]; j <= W; j++) {
        dp[0][j] = value[0];
    }
    for (int i = 1; i < n; i++) {          // 遍历物品
        for (int j = 0; j <= W; j++) {     // 遍历容量
            if (j < weight[i]) {
                // 装不下，只能不选
                dp[i][j] = dp[i - 1][j];
            } else {
                // 不选 vs 选，取较大值
                dp[i][j] = Math.max(dp[i - 1][j],
                        dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    return dp[n - 1][W];
}

时间复杂度 O(n·W)，空间 O(n·W)。

三、一维滚动数组：容量为什么必须倒序

观察递推公式可以发现：dp[i][j] 只依赖上一行的 dp[i-1][...]，更早的行根本没人用。于是可以压掉物品维度，只留一个一维数组，让它在物品循环里反复被"覆盖更新"：

public int knapsack01Rolling(int[] weight, int[] value, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < weight.length; i++) {          // 遍历物品
        for (int j = W; j >= weight[i]; j--) {         // 容量倒序！
            // dp[j - weight[i]] 此时仍是"上一行"的值（未在本轮被更新）
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

为什么内层必须倒序？ 核心是：倒序保证 dp[j - weight[i]] 还是上一轮物品（即"没考虑当前物品"）的旧值。画个表看得很清楚，假设第 i 件物品重量为 1、价值为 15，容量 W=4：

正序（错误）：j = 1, 2, 3, 4 依次更新
dp[1] = max(dp[1], dp[0] + 15) = 15   ← 用的是旧 dp[0]
dp[2] = max(dp[2], dp[1] + 15) = 30   ← dp[1] 已是本轮新值！物品被放了两次
dp[3] = max(dp[3], dp[2] + 15) = 45   ← 放了三次
dp[4] = max(dp[4], dp[3] + 15) = 60   ← 放了四次，01 背包变"无限背包"

倒序（正确）：j = 4, 3, 2, 1 依次更新
dp[4] = max(dp[4], dp[3] + 15)        ← dp[3] 还是旧值，最多放一次
dp[3] = max(dp[3], dp[2] + 15)        ← dp[2] 也还是旧值
...

一句话总结：倒序是从后往前"读旧写新"，正序会让本轮刚写入的新值污染后面的计算，导致同一物品被重复选取。

四、完全背包：正序遍历的原理

完全背包中每件物品可以选无限次，这时"重复选取"反而是合法的——所以把上面的一维写法改成正序遍历，就是完全背包：

public int knapsackComplete(int[] weight, int[] value, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int j = weight[i]; j <= W; j++) {         // 容量正序
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

正序时 dp[j - weight[i]] 是本轮的新值，含义是"当前物品已经可能被选过一次，还能再选"——恰好符合完全背包语义。01 背包与完全背包的一维写法只差一个循环方向，这个对照务必记牢。

五、组合数 vs 排列数：嵌套顺序之辨

完全背包还有一类变体：不问最大价值，问"凑出容量的方案数"。这时递推变成 dp[j] += dp[j - weight[i]]，而双层循环的嵌套顺序决定了统计的是组合还是排列：

求什么	外层	内层	直觉解释
组合数（{1,2} 和 {2,1} 算一种）	物品	容量	每轮只引入一件新物品，方案按"物品种类"划分，天然不重不漏
排列数（{1,2} 和 {2,1} 算两种）	容量	物品	每个容量都允许任意物品作最后一步，枚举出所有顺序

以 518. 零钱兑换 II（求组合数，coins 在外）和 377. 组合总和 IV（求排列数，target 在外）为例：

// 518 零钱兑换 II：求组合数 → 外层物品，内层容量
public 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];
}
 
// 377 组合总和 IV：求排列数 → 外层容量，内层物品
public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int j = 1; j <= target; j++) {        // 外层容量
        for (int num : nums) {                 // 内层物品
            if (j >= num) dp[j] += dp[j - num];
        }
    }
    return dp[target];
}

拿 3 个数凑 4 验证一下：组合口径下 {1,3} 只算 1 种；排列口径下 1+3 和 3+1 算 2 种。两者答案不同，全靠循环嵌套顺序区分。

六、实战应用：把普通题翻译成背包

416. 分割等和子集：数组能否分成两部分使两边和相等？设总和为 S，问题等价于：能否从数组中选出一些数，恰好凑出 S/2——把"数值"同时看作重量和价值，这就是一个"能否装满、最大价值是多少"的 01 背包判定：

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;            // 奇数直接不可能
    int target = sum / 2;
    int[] dp = new int[target + 1];            // dp[j]: 容量 j 能装的最大"和"
    for (int num : nums) {
        for (int j = target; j >= num; j--) {  // 01 背包，倒序
            dp[j] = Math.max(dp[j], dp[j - num] + num);
        }
    }
    return dp[target] == target;               // 能恰好凑出 target
}

1049. 最后一块石头的重量 II：每次把两块石头相消，剩差值的绝对值。要让最后剩下的石头最小，就要把石头分成两堆、使两堆总重尽量接近 total/2——和 416 同款转化：用 01 背包求出容量 total/2 内能凑出的最大和 most，答案就是 total - 2 * most。

七、复杂度与易错点

复杂度：01/完全背包时间均为 O(n·W)；01 背包空间 O(W)（滚动数组），二维写法 O(n·W)。

易错点清单：

01 背包一维优化忘记倒序，静默地把题解成了完全背包——输出不报错但数值偏大。
求组合/排列数时初始化写成 0：dp[0] 必须为 1（空集是唯一方案），否则全表为 0。
416 忘判 sum 的奇偶性，target 除出来是小数。
内层循环边界：01 背包倒序时 j >= weight[i]，写成 j > 0 会在 j < weight[i] 时读越界索引。
遍历顺序适用场景混淆：组合数题写成先容量后物品，答案会莫名偏大。

八、LeetCode 题目清单

题号	题名	一句话考点
416	分割等和子集	能否恰好装满 S/2 的 01 背包判定
1049	最后一块石头的重量 II	对半分转化成 01 背包求最接近的和
494	目标和	加减号选择转化为子集和计数
474	一和零	重量是"0 的个数和 1 的个数"的二维费用背包
518	零钱兑换 II	完全背包求组合数，外物内背
377	组合总和 IV	完全背包求排列数，外背内物
322	零钱兑换	完全背包求最少件数
279	完全平方数	物品是 1,4,9,... 的完全背包
139	单词拆分	排列型完全背包判断字符串可达

参考

代码随想录 · 背包问题