背包问题深度解析：0-1 背包、完全背包与空间压缩

摘要

背包问题是动态规划中最重要的经典模型之一，它直接对应了面试中大量”是否能凑成目标值”、“最少需要多少个”、“有多少种方案”类型的题目。本文从 0-1 背包的二维 DP 推导出发，一步步推演到一维滚动数组优化，彻底揭示”为什么 0-1 背包要逆序遍历、完全背包要正序遍历”这个面试高频考点。掌握本文，能让你在遇到任何背包变体时，迅速判断”这是哪种背包”，并正确写出一维 DP。

第 1 章背包问题的定义与分类

1.1 经典背包问题的形式化定义

0-1 背包：有 $n$ 件物品，第 $i$ 件物品的重量为 $w_{i}$ ，价值为 $v_{i}$ 。背包容量为 $W$ 。每件物品只能选一次（选 1 次或 0 次），求在不超过容量 $W$ 的条件下能装入的最大价值。

完全背包：同上，但每件物品可以无限次选取。

多重背包：同上，但第 $i$ 件物品最多选 $c_{i}$ 次。

分组背包：物品被分成若干组，每组内最多只能选一件物品。

面试中最常考的是前两种，本文重点讲透这两种，并给出 LeetCode 对应题目。

1.2 为什么要把背包问题理解透

背包问题之所以重要，不是因为面试会直接考”0-1 背包”，而是因为大量看似无关的题目，其本质都是背包的变形：

“能否用给定数字凑成目标值 target”→ 0-1 背包或完全背包（判断问题）
“最少用几枚硬币凑成金额 amount” → 完全背包（最小化问题）
“有多少种方案凑成目标” → 背包计数问题
“数组能否被分成两个等和子集” → 0-1 背包

背包问题的核心，是”容量”和”物品”的二维关系。理解了这个关系，遇到类似题目时能够快速建模。

第 2 章 0-1 背包：二维 DP 推导

2.1 状态定义

状态：dp[i][j] = 考虑了前 i 件物品（编号 1 到 i），背包容量为 j 时，能装入的最大价值。

注意：dp[i][j] 中的”考虑了前 i 件物品”不等于”一定装了前 i 件物品”——它是”在只允许使用前 i 件物品的前提下的最优结果”。

2.2 状态转移方程

对第 i 件物品（重量 w[i]，价值 v[i]），有两个选择：

不装第 i 件物品：

$d p [i] [j] = d p [i - 1] [j]$

背包中不装第 i 件，最大价值等于只考虑前 i-1 件时容量 j 的最大价值。

装第 i 件物品（前提：j >= w[i]）：

$d p [i] [j] = d p [i - 1] [j - w [i]] + v [i]$

装了第 i 件，消耗容量 w[i]，价值增加 v[i]；剩余容量 j - w[i] 由前 i-1 件物品填充。

两种情况取最大值：

$d p [i] [j] = max (d p [i - 1] [j], d p [i - 1] [j - w [i]] + v [i]) (j \geq w [i])$

当 j < w[i] 时，装不下第 i 件：

$d p [i] [j] = d p [i - 1] [j]$

2.3 初始化

dp[0][j] = 0 for all j（没有物品，价值为 0）
dp[i][0] = 0 for all i（容量为 0，无法装任何物品）

2.4 二维 DP 完整实现

int knapsack01(int[] weights, int[] values, int W) {
    int n = weights.length;
    // dp[i][j] = 考虑前 i 件物品、容量为 j 时的最大价值
    int[][] dp = new int[n + 1][W + 1];
 
    // 初始化：dp[0][*] = 0，dp[*][0] = 0（Java 默认 int 数组初始化为 0）
 
    for (int i = 1; i <= n; i++) {
        int w = weights[i - 1];  // 第 i 件物品的重量（0-indexed 数组）
        int v = values[i - 1];   // 第 i 件物品的价值
 
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i - 1][j];  // 不装第 i 件
 
            if (j >= w) {
                // 装第 i 件：从容量 j-w 的前 i-1 件最优解转移
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w] + v);
            }
        }
    }
    return dp[n][W];
}

时间复杂度： $O (nW)$ ，空间复杂度： $O (nW)$ 。

第 3 章 0-1 背包：一维滚动数组优化

3.1 观察依赖关系

观察二维 DP 的转移方程：

$d p [i] [j] = max (d p [i - 1] [j], d p [i - 1] [j - w] + v)$

dp[i][j] 只依赖于第 i-1 行的数据，不依赖更早的行。这意味着，在计算第 i 行时，第 i-2、i-3、… 行的数据已经不需要了，可以只保留一行（一维数组）滚动推进。

3.2 一维压缩的推导

把二维 dp[i][j] 压缩为一维 dp[j]（只保留当前行）：

在每轮（第 i 件物品），把”上一行 dp[i-1][j]”的值就地更新为”当前行 dp[i][j]”。

但这里有个陷阱：如果从左往右正序更新 dp[j]，那么计算 dp[j] 时用到的 dp[j-w] 已经被本轮更新过了——它不再是 dp[i-1][j-w]，而是 dp[i][j-w]，相当于物品 i 被”使用了两次”。

0-1 背包要求每件物品最多用一次，因此不能让 dp[j-w] 在同一轮被更新后再被引用。

解决方法：逆序遍历 j，从 W 到 w。

逆序遍历时，计算 dp[j] 时用到的 dp[j-w]（j-w < j）尚未被本轮更新，仍然是上一行的值。这样就保证了 0-1 背包”每件物品只用一次”的语义。

int knapsack01_1D(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[] dp = new int[W + 1];  // dp[j] = 容量为 j 时的最大价值
 
    for (int i = 0; i < n; i++) {
        int w = weights[i];
        int v = values[i];
        // ⚠️ 逆序遍历！从 W 到 w（不能到 0，因为 j < w 时装不下）
        for (int j = W; j >= w; j--) {
            dp[j] = Math.max(dp[j],      // 不装物品 i
                             dp[j - w] + v);  // 装物品 i
        }
    }
    return dp[W];
}

核心概念：为什么 0-1 背包逆序遍历

逆序遍历保证了：计算 dp[j] 时引用的 dp[j-w] 还是**上一轮（上一件物品）**的值，而不是本轮已经更新后的值。正序遍历时，dp[j-w] 已被本轮更新，相当于允许物品被多次使用——那就变成了完全背包。 一句话：逆序 = 0-1 背包（每件只用一次）；正序 = 完全背包（每件可用无限次）。

第 4 章完全背包：正序遍历的原因

4.1 完全背包与 0-1 背包的区别

完全背包中，每件物品可以无限次使用。转移方程变为：

$d p [i] [j] = max (d p [i - 1] [j], d p [i] [j - w [i]] + v [i])$

注意：装物品 i 的情况变成了 dp[i][j-w] + v，而不是 dp[i-1][j-w] + v——因为装了一次物品 i 之后，剩余容量内还可以再装物品 i，所以引用的是同一行（第 i 行）的结果，而非上一行。

4.2 一维版本：正序遍历

把完全背包压缩为一维数组时，计算 dp[j] 引用的 dp[j-w] 正好应该是本轮已经更新的值（即允许物品 i 被多次使用）。因此，完全背包用正序遍历：

int knapsackComplete(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[] dp = new int[W + 1];
 
    for (int i = 0; i < n; i++) {
        int w = weights[i];
        int v = values[i];
        // ✅ 正序遍历！允许物品 i 被多次使用
        for (int j = w; j <= W; j++) {
            dp[j] = Math.max(dp[j], dp[j - w] + v);
        }
    }
    return dp[W];
}

4.3 两种背包的对比

背包类型	物品使用次数	二维转移（装物品 i）	一维遍历方向
0-1 背包	最多 1 次	`dp[i-1][j-w] + v`（上一行）	逆序（W 到 w）
完全背包	无限次	`dp[i][j-w] + v`（本行）	正序（w 到 W）

第 5 章 LeetCode 416：分割等和子集

5.1 题目

LeetCode 416 - Partition Equal Subset Sum（中等）

给你一个只包含正整数的非空数组 nums，请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

输入: nums = [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11]。

输入: nums = [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个等和子集。

5.2 问题建模

等和子集分割的必要条件是：数组总和 sum 必须是偶数（否则不可能等分）。如果 sum 是偶数，目标是找一个子集，使其元素和等于 sum / 2。

这就是 0-1 背包问题：

物品：nums 的每个元素（重量 = 价值 = 元素值）
背包容量：sum / 2
目标：能否恰好装满容量为 sum / 2 的背包

这是背包的判断型变体（不是求最大价值，而是判断”是否可以恰好装满”）。

5.3 状态定义与转移

状态：dp[j] = 是否可以从数组中选若干元素，使其总和恰好为 j。

初始值：dp[0] = true（空集，和为 0，一定可以），其他 dp[j] = false。

转移方程（0-1 背包，逆序遍历）：

$d p [j] = d p [j] OR d p [j - nums [i]]$

含义：如果不选 nums[i]，保持 dp[j] 不变；如果选 nums[i]，则 dp[j] = “之前是否能凑出 j - nums[i]”。

5.4 完整实现

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
 
    // 总和为奇数，无法等分
    if (sum % 2 != 0) return false;
 
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;  // 空集和为 0，一定可以
 
    for (int num : nums) {
        // 0-1 背包：逆序遍历，保证每个 num 只用一次
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
        // 提前终止：如果已经能凑出 target，直接返回
        if (dp[target]) return true;
    }
    return dp[target];
}

时间复杂度： $O (n \times target) = O (n \times sum /2)$ 。 空间复杂度： $O (target)$ 。

5.5 边界分析

情况一：nums = [1, 1] sum = 2, target = 1。遍历 num = 1：dp[1] = dp[0] = true。返回 true。✅

情况二：nums = [1, 2, 3, 5] sum = 11（奇数），直接返回 false。✅

情况三：nums = [2, 2, 1, 1] sum = 6, target = 3。

处理 num = 2：dp[2] = dp[0] = true
处理 num = 2：dp[4] = dp[2] = true（但 4 > target = 3，不在范围内）；dp[2] 逆序处理，先 dp[3] = dp[1]（false），再 dp[2] = dp[0]（true，已是 true）
处理 num = 1：逆序：dp[3] = dp[2] = true 返回 true。✅

第 6 章 LeetCode 322：零钱兑换

6.1 题目

LeetCode 322 - Coin Change（中等）

给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。计算凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

输入: coins = [1, 5, 10, 25], amount = 36
输出: 3
解释: 25 + 10 + 1 = 36，使用 3 枚。

输入: coins = [2], amount = 3
输出: -1

6.2 建模为完全背包

每种硬币可以无限次使用 → 完全背包。

但这次求的是”最少硬币数”（最小化问题），而不是”最大价值”。

状态：dp[j] = 凑成金额 j 所需的最少硬币数。

初始值：

dp[0] = 0（金额为 0，不需要任何硬币）
dp[j] = Integer.MAX_VALUE / 2（代表”无法凑成”，用 MAX_VALUE / 2 而非 MAX_VALUE 防止加法溢出）

转移方程（完全背包，正序遍历）：

$d p [j] = min (d p [j], d p [j - coin] + 1)$

含义：用 coin 面额的硬币一枚，凑成 j - coin 的最少方案数加 1，与不用这枚硬币的方案数取最小。

public 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++) {
            if (dp[j - coin] != amount + 1) {  // dp[j-coin] 可达
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
    }
 
    return dp[amount] > amount ? -1 : dp[amount];
}

为什么用 amount + 1 而非 Integer.MAX_VALUE 作为初始值？

如果用 Integer.MAX_VALUE，则 dp[j-coin] + 1 会溢出（MAX_VALUE + 1 变成负数），导致错误结果。用 amount + 1 是一个安全的”无穷大”——因为最坏情况下（全用 1 元硬币）需要 amount 枚，所以合法答案不超过 amount，初始化为 amount + 1 能正确表示”不可达”。

6.3 遍历顺序：为什么外层是硬币、内层是金额

有人可能会问：能不能把循环顺序交换，外层遍历金额，内层遍历硬币？

// 写法 B：外层金额，内层硬币
for (int j = 1; j <= amount; j++) {
    for (int coin : coins) {
        if (j >= coin && dp[j - coin] != amount + 1) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
}

对于”最少硬币数”这道题，两种写法的结果是一样的，因为完全背包中每种硬币无限次可用，遍历顺序不影响最终结果。

但对于”方案数”（见下文），遍历顺序会影响是否区分不同顺序，必须注意。

第 7 章 LeetCode 518：零钱兑换 II（方案数）

7.1 题目

LeetCode 518 - Coin Change II（中等）

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0。假设每一种面值的硬币有无限个。

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额：
     5=5
     5=2+2+1
     5=2+1+1+1
     5=1+1+1+1+1

7.2 组合数 vs 排列数：遍历顺序的关键差异

这道题求的是组合数（不同顺序的相同硬币集合只算一种）。

{1,2,2} 和 {2,1,2} 和 {2,2,1} 算同一种组合。

与之对应的另一种题是求排列数（LeetCode 377 Combination Sum IV）——不同顺序算不同方案。

关键结论：

目标	外层遍历	内层遍历
组合数（不计顺序）	硬币（物品）	金额（容量）
排列数（计顺序）	金额（容量）	硬币（物品）

为什么外层遍历硬币能保证是组合数？因为硬币是按固定顺序遍历的（假设硬币 1 在硬币 2 前面），那么任何包含硬币 1 和硬币 2 的方案，都会在”处理硬币 1”时算入先使用硬币 1 的路径中，不会在”处理硬币 2”时被重复计算。

7.3 完整实现

// 组合数版本（外层物品，内层容量）
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];
}
 
// 排列数版本（外层容量，内层物品）—— LeetCode 377
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];
}

生产避坑：组合数 vs 排列数

“外层物品，内层容量”→ 组合数（同一组合不重复计算） “外层容量，内层物品”→ 排列数（同一组合的不同排列各计一次）在面试中，一定要先确认题目要求的是组合还是排列，再决定循环嵌套顺序。

第 8 章 LeetCode 474：一和零（二维背包）

8.1 题目

LeetCode 474 - Ones and Zeroes（中等）

给你一个二进制字符串数组 strs 和两个整数 m 和 n。请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1。

输入: strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出: 4
解释: 最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，大小为 4 。

8.2 二维背包的建模

这道题有两个容量限制（0 的个数上限 m 和 1 的个数上限 n），是 0-1 背包的二维版本。

状态：dp[i][j] = 在使用最多 i 个 0 和最多 j 个 1 的条件下，能选取的最多字符串数量。

转移方程：对每个字符串 s（设它有 zeros 个 0 和 ones 个 1）：

$d p [i] [j] = max (d p [i] [j], d p [i - zeros] [j - ones] + 1)$

与 0-1 背包一维压缩类似，这里使用逆序遍历两个容量维度（因为每个字符串只能选一次）：

public int findMaxForm(String[] strs, int m, int n) {
    int[][] dp = new int[m + 1][n + 1];  // dp[i][j] = 最多用 i 个0, j 个1 能选的最多字符串数
 
    for (String s : strs) {
        // 统计当前字符串中 0 和 1 的数量
        int zeros = 0, ones = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') zeros++;
            else ones++;
        }
 
        // 二维 0-1 背包：逆序遍历两个维度
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
            }
        }
    }
    return dp[m][n];
}

第 9 章背包问题的完整知识框架

9.1 决策树：如何识别是哪种背包

遇到"从给定集合中选元素凑目标"的问题
   ↓
每个元素能用几次？
   ├── 最多 1 次 → 0-1 背包（逆序遍历）
   ├── 无限次   → 完全背包（正序遍历）
   └── 最多 k 次 → 多重背包（二进制拆分转化为 0-1 背包）
   ↓
目标类型？
   ├── 最大价值/最多个数 → max 型转移
   ├── 最少个数/最小代价 → min 型转移
   ├── 恰好等于某个值（是否可行） → bool 型转移（OR）
   └── 方案总数 → 计数型转移（+=）
   ↓
是否区分选取顺序？
   ├── 不区分（组合数）→ 外层物品，内层容量
   └── 区分（排列数）  → 外层容量，内层物品

9.2 背包问题 LeetCode 高频题汇总

题号	题目	背包类型	核心技巧
416	Partition Equal Subset Sum	0-1 背包（判断）	bool DP，逆序遍历
494	Target Sum	0-1 背包（计数）	转化为恰好凑 target 的方案数
474	Ones and Zeroes	二维 0-1 背包	两个容量维度，二维逆序
322	Coin Change	完全背包（最小值）	min DP，正序遍历
518	Coin Change II	完全背包（计数，组合）	外层物品，正序遍历
377	Combination Sum IV	完全背包（计数，排列）	外层容量，内层物品
279	Perfect Squares	完全背包（最小值）	完全平方数作为”物品”
139	Word Break	完全背包（判断）	字符串完全背包，dp[i] 表示前 i 个字符能否分割

9.3 背包问题的初始化陷阱

背包问题的初始化因”目标类型”不同而不同，务必区分：

最大价值类（max 型）：

dp[0] = 0，其他 dp[j] = 0
含义：没有物品时，任何容量的最大价值都是 0（什么都没装）

判断可行性类（bool 型）：

dp[0] = true，其他 dp[j] = false
含义：凑出 0 是可行的（空集），其他金额初始不可达

最小代价类（min 型）：

dp[0] = 0，其他 dp[j] = +∞
含义：凑出 0 代价为 0，其他金额初始不可达（用大数代表 +∞）

计数类（count 型）：

dp[0] = 1，其他 dp[j] = 0
含义：凑出 0 有 1 种方案（空集），其他金额初始没有方案

生产避坑：最小值类背包的溢出

最小值类背包用 Integer.MAX_VALUE 初始化时，dp[j-coin] + 1 会溢出（-2147483648）。安全做法：用 amount + 1 或 target + 1 作为初始”无穷大”，因为合法答案必然小于这个值。

小结

本文从 0-1 背包的二维 DP 推导出发，彻底揭示了”一维滚动数组”的本质：

0-1 背包逆序：保证每件物品最多使用一次，dp[j-w] 引用的是上一轮未更新的值
完全背包正序：允许同一件物品多次使用，dp[j-w] 引用的是本轮已更新的值
组合 vs 排列：外层物品/内层容量 → 组合数；外层容量/内层物品 → 排列数
初始化因目标类型而异：最大值/计数初始 0 和 1；最小值/判断初始 +∞ 和 false

下一篇子序列DP：最长递增子序列与O(nlogn)优化将介绍另一大类 DP：以序列为对象、以子序列为目标的最优化问题，重点讲解 LIS 的 $O (n^{2})$ 推导和 $O (n lo g n)$ 优化。

汀的知识碎片

文章导航

03 背包问题深度解析：0-1背包、完全背包与空间压缩

背包问题深度解析：0-1 背包、完全背包与空间压缩

摘要

第 1 章 背包问题的定义与分类

1.1 经典背包问题的形式化定义

1.2 为什么要把背包问题理解透

第 2 章 0-1 背包：二维 DP 推导

2.1 状态定义

2.2 状态转移方程

2.3 初始化

2.4 二维 DP 完整实现

第 3 章 0-1 背包：一维滚动数组优化

3.1 观察依赖关系

3.2 一维压缩的推导

第 4 章 完全背包：正序遍历的原因

4.1 完全背包与 0-1 背包的区别

4.2 一维版本：正序遍历

4.3 两种背包的对比

第 5 章 LeetCode 416：分割等和子集

5.1 题目

5.2 问题建模

5.3 状态定义与转移

5.4 完整实现

5.5 边界分析

第 6 章 LeetCode 322：零钱兑换

6.1 题目

6.2 建模为完全背包

6.3 遍历顺序：为什么外层是硬币、内层是金额

第 7 章 LeetCode 518：零钱兑换 II（方案数）

7.1 题目

7.2 组合数 vs 排列数：遍历顺序的关键差异

7.3 完整实现

第 8 章 LeetCode 474：一和零（二维背包）

8.1 题目

8.2 二维背包的建模

第 9 章 背包问题的完整知识框架

9.1 决策树：如何识别是哪种背包

9.2 背包问题 LeetCode 高频题汇总

9.3 背包问题的初始化陷阱

小结

On this page

第 1 章背包问题的定义与分类

第 4 章完全背包：正序遍历的原因

第 9 章背包问题的完整知识框架