动态规划背包九讲：从01背包到树形DP的算法核心精解

1. 项目概述：从“一个旅行者的背包”到算法竞赛的基石

如果你刚开始接触算法，尤其是动态规划，那么“背包问题”几乎是你绕不开的第一座大山。我第一次被它“折磨”是在大学的一次算法课上，老师用“一个旅行者有一个最多能装 M 公斤的背包，现在有 N 件物品…”这个经典描述引入时，我满脑子想的都是怎么塞下最多的零食。但当我真正去解它，才发现这小小的背包里，装的不仅是物品，更是一整套解决复杂资源分配问题的思维框架。背包问题之所以经典，是因为它抽象了“在有限资源（背包容量）下，从若干选项（物品）中进行选择以最大化收益”这一核心场景，这个场景在现实世界中无处不在，从投资组合优化到云计算资源调度，底层逻辑都是相通的。

所谓的“背包九讲”，并非指九篇独立的讲义，而是对背包问题这一大类问题的系统性梳理和归纳，通常涵盖了从最基础的01背包、完全背包到更复杂的多重背包、混合背包，乃至二维费用背包、分组背包、有依赖的背包等九种核心变体。掌握它们，意味着你掌握了用动态规划解决组合优化问题的一把万能钥匙。本文将结合我多年刷题和教学的经验，为你逐一拆解这九种背包问题的核心思路、状态定义、转移方程，并提供清晰的 C++ 代码实现与分析。无论你是正在备战算法竞赛的学生，还是希望夯实动态规划基础的开发者，这篇文章都将带你从“为什么这样设计”的角度，彻底吃透背包问题。

2. 动态规划与背包问题的核心思想

在深入九种具体问题之前，我们必须先统一思想：动态规划（DP）到底在做什么？很多人一上来就背“状态”、“转移方程”，却忽略了其本质。你可以把 DP 想象成一种“聪明的枚举”。对于背包问题，暴力解法是枚举每件物品“选”或“不选”的所有组合（共 2^N 种），然后检查是否超重并计算价值。这在大数据量下是指数爆炸的，不可行。

DP 的聪明之处在于“记忆化”和“最优子结构”。它把大问题（考虑前 i 件物品、容量为 j 的背包）分解成小问题（考虑前 i-1 件物品、容量为 j 或 j-w[i] 的背包）。关键在于，我们只关心“最大价值”这个结果，而不关心中间具体选了哪些物品的组合。因此，我们可以用一个数组dp[i][j]来记录“只考虑前 i 件物品，在背包容量恰好为 j 的情况下，能获得的最大价值”。这个dp数组就是我们的“记忆本”。

注意：这里有一个初学者极易混淆的点。dp[i][j]的定义中，“容量恰好为 j”和“容量不超过 j”在初始化和最终答案处理上有所不同。为了简化理解和代码，后续我们大多采用“不超过 j”的定义，即dp[i][j]表示考虑前 i 件物品，背包容量不超过 j 时的最大价值。这样最终答案就是dp[N][M]，初始化也简单（全部为0）。但在一些变种问题中，“恰好”的定义可能更合适，需要特别注意。

背包问题的状态转移，核心就是做决策：对于第 i 件物品，在容量 j 下，我们有两种选择（以01背包为例）：

1. 不选：那么最大价值就等于考虑前 i-1 件物品、容量为 j 时的最大价值，即dp[i][j] = dp[i-1][j]。
2. 选（前提是能装下，即j >= weight[i]）：那么最大价值就等于“物品 i 的价值”加上“考虑前 i-1 件物品、剩余容量为j - weight[i]时的最大价值”，即dp[i][j] = value[i] + dp[i-1][j - weight[i]]。

我们的目标就是在这两种决策中取最大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])。这个方程就是背包问题的灵魂。

3. 基石：01背包问题的深度剖析与空间优化

01背包是所有背包问题的起点。问题描述：有 N 件物品和一个容量为 V 的背包。第 i 件物品的重量是w[i]，价值是v[i]。每件物品只有一件，可以选择放或不放。求解将哪些物品装入背包可使总价值最大。

3.1 二维DP模板与直观理解

最直观的方法是使用二维数组dp[i][j]。根据上面的分析，核心代码如下：

vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0)); for (int i = 1; i <= N; ++i) { // 遍历物品 for (int j = 0; j <= V; ++j) { // 遍历容量 // 不选第i件物品 dp[i][j] = dp[i-1][j]; // 如果能放下，尝试选第i件物品 if (j >= w[i]) { dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]); } } } int ans = dp[N][V];

这个双重循环是 DP 的经典结构。外层循环遍历物品，意味着我们逐个考虑是否将物品加入决策集合；内层循环遍历容量，计算在当前考虑的物品范围内，不同容量限制下的最优解。dp[i][j]的值只依赖于上一行i-1的数据，这为空间优化提供了可能。

3.2 一维滚动数组优化（核心技巧）

观察状态转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，当前状态dp[i][j]仅由dp[i-1][...]也就是上一行的状态推导而来。那我们是否可以只用一个一维数组dp[j]来表示“当前考虑物品阶段下，容量为 j 的最大价值”呢？

答案是肯定的，但内层循环的遍历顺序必须颠倒。我们定义一维数组dp[j]，其含义是：在遍历到当前物品时，背包容量为 j 所能获得的最大价值。关键代码如下：

vector<int> dp(V + 1, 0); for (int i = 1; i <= N; ++i) { // 遍历物品 for (int j = V; j >= w[i]; --j) { // 关键：倒序遍历容量 dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } int ans = dp[V];

为什么必须倒序（从V到w[i]）？我们来模拟一下。假设物品 i 重量为 2，价值为 5。

• 如果正序遍历（j从w[i]到V）：当计算dp[4]时，dp[4] = max(dp[4], dp[2] + 5)。注意，此时的dp[2]可能已经在本次物品 i 的循环中被更新过了（即dp[2]已经考虑了放入物品 i 的情况）。这意味着，在计算dp[4]时，我们可能使用了“已经放入过一次物品 i 的dp[2]”，这相当于物品 i 被放入了多次，违背了01背包“每个物品仅一件”的约束。
• 如果倒序遍历（j从V到w[i]）：当计算dp[4]时，dp[2]还没有被本次循环更新，它保存的还是“考虑前 i-1 件物品”时的状态。这样就保证了每件物品只被计算一次。

实操心得：一维优化是必须掌握的核心技巧，它极大节省了空间。务必牢记“01背包倒序，完全背包正序”这个口诀。在笔试或竞赛中，除非题目明确要求记录路径，否则一律使用一维写法。

3.3 初始化与边界条件的陷阱

初始化dp数组看似简单，实则暗藏玄机，它直接关联到我们对dp[j]的定义。

• 如果定义dp[j]为“容量不超过j 的最大价值”，那么将所有dp[j]初始化为 0 是合理的。因为不放任何物品时，任何容量下的最大价值都是0。
• 如果定义dp[j]为“容量恰好为 j 的最大价值”，那么初始化应为dp[0] = 0（容量为0时价值为0），而dp[1...V] = -INF（负无穷，或一个非常小的数）。这是因为除了容量0，其他容量在未放入任何物品时是无法“恰好达到”的，初始状态应视为无效。最终答案也不是dp[V]，而是max(dp[0...V])。

在大多数情况下，我们使用“不超过”的定义，初始化全0即可。但在一些变种问题，如“能否恰好装满背包”、“装满背包的方案数”等，就必须使用“恰好”的定义和对应的初始化。

4. 完全背包：物品无限供应下的策略转变

完全背包问题：每种物品有无限件可用。这是继01背包后第二个需要掌握的模型。

4.1 思路转变：从“选或不选”到“选多少件”

在01背包中，对于物品 i，决策是二元（0或1）。在完全背包中，决策变成了“选0件、1件、2件…直到放不下为止”。最朴素的想法是在状态转移时再加一层循环 k，遍历选取的件数：dp[i][j] = max(dp[i-1][j - k*w[i]] + k*v[i])，其中0 <= k*w[i] <= j。但这样时间复杂度会上升到 O(NVΣ(V/wi))，在物品重量很小时效率极低。

4.2 优化推导与一维正序实现

我们可以优化这个思路。对比01背包的方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)，完全背包的方程可以优化为dp[i][j] = max(dp[i-1][j], dp[i][j-w]+v)。区别在哪里？注意第二个来源是dp[i][j-w]+v，而不是dp[i-1][j-w]+v。这是因为，既然物品 i 无限件，那么在考虑“再放一件 i”时，其基础状态dp[i][j-w]可能已经放入过若干件物品 i 了。这允许了物品 i 的重复选取。

基于这个优化后的二维方程，我们同样可以压缩到一维。状态转移为：dp[j] = max(dp[j], dp[j - w[i]] + v[i])。神奇的是，它和01背包的一维转移方程一模一样。唯一的区别就在于内层循环的遍历顺序。

完全背包必须正序遍历容量：

vector<int> dp(V + 1, 0); for (int i = 1; i <= N; ++i) { // 遍历物品 for (int j = w[i]; j <= V; ++j) { // 关键：正序遍历容量 dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } int ans = dp[V];

为什么正序？我们同样模拟。计算dp[4]时，dp[2]可能已经被本次循环更新（即已经考虑过多放一件物品 i），那么dp[4] = max(dp[4], dp[2] + v[i])就相当于在dp[2]（可能已包含物品 i）的基础上再添加一件 i，这正好符合“物品无限件”的设定。

注意事项：这里物品的遍历顺序（外层循环）和容量的遍历顺序（内层循环）不能随意调换。在完全背包的一维写法中，先遍历物品，再遍历容量，得到的是“组合数”类型的解，即考虑物品的顺序是固定的（{物品1，物品2}和{物品2，物品1}被视为同一种组合）。如果调换顺序，先遍历容量再遍历物品，得到的是“排列数”类型的解，顺序不同的被视为不同方案。这在求解“装满背包的方案数”问题时至关重要。

5. 多重背包：当物品有了数量限制

多重背包问题：第 i 种物品最多有s[i]件可用。它介于01背包（1件）和完全背包（无限件）之间。

5.1 二进制拆分优化（将多重背包转化为01背包）

最直接的想法是把有s[i]件的物品 i，拆分成s[i]个独立的“01物品”，然后套用01背包。但当s[i]很大时（比如2000），物品总数会爆炸，复杂度 O(V*Σs[i]) 可能无法接受。

二进制拆分是一种极其巧妙的优化。其核心思想是：任何正整数都可以用一系列2的幂次数的和来表示。我们不是拆成s[i]个1，而是拆成若干个“系数为 2^k 的物品包”。例如，对于s[i]=13的物品，我们可以拆成系数为 1, 2, 4, 6 的四个“新物品”（因为 1+2+4+6=13）。其中1,2,4是2的幂次（2^0, 2^1, 2^2），最后的6是剩余的数量（13-1-2-4=6）。这样，通过选或不选这4个新物品，我们可以组合出0到13之间任意数量的原物品 i。

为什么这样有效？因为用1,2,4,6可以表示0-13的所有整数。这比拆13个1效率高得多。拆分后，对每个新物品（重量为k*w[i]，价值为k*v[i]）做一次01背包决策即可。复杂度优化为 O(V*Σlog s[i])。

// 假设物品信息已存储在 vectors w, v, s 中，索引从1开始 vector<int> dp(V + 1, 0); for (int i = 1; i <= N; ++i) { // 二进制拆分 int num = s[i]; for (int k = 1; k <= num; k *= 2) { // k 是2的幂次：1,2,4,8... int weight = k * w[i]; int value = k * v[i]; // 01背包过程（倒序） for (int j = V; j >= weight; --j) { dp[j] = max(dp[j], dp[j - weight] + value); } num -= k; } // 处理剩下的部分（如上面例子中的6） if (num > 0) { int weight = num * w[i]; int value = num * v[i]; for (int j = V; j >= weight; --j) { dp[j] = max(dp[j], dp[j - weight] + value); } } } int ans = dp[V];

5.2 单调队列优化（进一步追求效率）

对于数据规模极大的情况，还可以使用单调队列优化，将复杂度进一步降至 O(N*V)。其思路是利用滑动窗口求最大值的特性，优化内层循环。但由于实现相对复杂，且二进制拆分在绝大多数竞赛和面试中已足够，此处不展开代码细节。你需要知道的是，当题目数据范围极大（如 V 和 Σs[i] 都在10^4以上）时，单调队列优化是可行的终极手段。

6. 混合背包与二维费用背包

6.1 混合背包：多种类型的物品共存

混合背包问题，简单说就是：有的物品只能取一次（01背包），有的物品能取无限次（完全背包），有的物品能取有限次（多重背包）。解决方案很直接：分类处理。

在遍历物品时，判断当前物品的类型：

• 如果是01背包，就用倒序的一维循环处理。
• 如果是完全背包，就用正序的一维循环处理。
• 如果是多重背包，就先进行二进制拆分，将拆分出的每个“物品包”当作01背包物品处理。

代码结构清晰，相当于把前面几种背包的代码模块组合起来。

6.2 二维费用背包：约束条件多了一个维度

二维费用背包问题：对于每件物品，除了重量w[i]这个费用，还有第二个费用（比如体积u[i]）。背包也有两个最大限制：重量容量V和体积容量U。每件物品只能选择一次（01规则）或无限次（完全规则）。

思路是将状态数组升维。我们定义dp[j][k]表示在重量不超过 j、体积不超过 k 的条件下的最大价值。状态转移方程是01背包或完全背包的二维费用版本。

以01背包规则为例，一维优化后的核心代码（注意是两层费用循环，且都需要倒序）：

vector<vector<int>> dp(V + 1, vector<int>(U + 1, 0)); for (int i = 1; i <= N; ++i) { for (int j = V; j >= w[i]; --j) { // 费用1倒序 for (int k = U; k >= u[i]; --k) { // 费用2倒序 dp[j][k] = max(dp[j][k], dp[j - w[i]][k - u[i]] + v[i]); } } } int ans = dp[V][U];

如果是完全背包规则，则将两层内循环都改为正序即可。这可以很容易地推广到“多维费用”背包，每多一维约束，状态数组和循环就多一维。

7. 分组背包与有依赖的背包

7.1 分组背包：组内互斥的选择

分组背包问题：物品被划分为若干组，每组内的物品相互冲突，最多只能选择其中一件。求解最大价值。

这引入了“组”的概念。我们的决策变成了：对于每一组，我们要决定选择组内的哪一件物品，或者一件都不选。状态定义可以沿用dp[j]，表示容量为 j 时的最大价值。

核心的遍历顺序是三层循环，但理解其逻辑至关重要：

1. 第一层循环：遍历每一个组。
2. 第二层循环：遍历背包容量j（必须倒序，因为每组内最多选一个，类似于01背包）。
3. 第三层循环：遍历当前组内的每一个物品k。

关键点在于，对于固定的组i和固定的容量j，我们遍历组内所有物品k，尝试用物品k更新dp[j]。由于容量循环是倒序的，保证了组内物品不会重复选取。

// 假设有 K 个组，每组物品信息存储为 vectors vector<int> dp(V + 1, 0); for (int i = 0; i < K; ++i) { // 遍历每个组 for (int j = V; j >= 0; --j) { // 容量倒序遍历 for (auto& item : groups[i]) { // 遍历组内每个物品 int weight = item.w, value = item.v; if (j >= weight) { dp[j] = max(dp[j], dp[j - weight] + value); } } } } int ans = dp[V];

7.2 有依赖的背包：树形DP的引入

有依赖的背包问题通常表现为物品间存在主件和附件的依赖关系，例如：要选附件，必须先选其主件。这形成了一个树形结构（每个主件及其附件构成一棵子树）。

解决这类问题需要结合树形DP和分组背包的思想。通常以深度优先搜索（DFS）的方式遍历这棵树。对于以节点u（主件）为根的子树，我们将其视为一个“物品组”。但这个“物品”不是单一的，而是包含了选择以u为根的子树的各种可能方案（即花费不同容量，获得不同价值）。

处理流程：

1. DFS 递归处理：先递归处理所有子节点（附件），得到每个子节点在不同容量下的最优价值（即它们各自的dp数组）。
2. 合并分组：将当前主件u视为一个必选物品（花费w[u]，价值v[u]）。然后，它的每个子节点（附件）都对应一组选择方案（选或不选该附件，以及如果选，花多少钱）。我们需要将这些子节点的方案，与主件进行组合。
3. 分组背包决策：这个过程实质上是一个分组背包。主件u本身是必选的基底。对于每个子节点child，我们有一系列决策（即child的dp_child[0...V]数组）。我们需要从这些决策中，为整个子树选择一个总花费不超过剩余容量的方案。这可以通过一个动态规划合并过程来实现，通常使用一个临时数组f来模拟分组背包的更新。

由于代码较长且涉及树形结构，这里给出核心伪代码思路：

void dfs(int u) { // 初始化，必须选择主件u for (int j = V; j >= w[u]; --j) { dp_u[j] = v[u]; // dp_u 是当前子树的结果数组 } // 遍历所有附件（子节点） for (int child : children[u]) { dfs(child); // 处理子节点，得到其 dp_child // 分组背包合并过程 for (int j = V; j >= w[u]; --j) { // 当前可用总容量 for (int k = 0; k <= j - w[u]; ++k) { // 分配给子节点 child 的容量 dp_u[j] = max(dp_u[j], dp_u[j - k] + dp_child[k]); // 注意：这里的 dp_u[j-k] 是尚未用 child 更新的“旧值” // 实际编码中通常需要一个临时数组 temp 来保证正确性 } } } }

有依赖的背包是背包问题中难度较高的一类，需要熟练掌握树形DP和分组背包的融合。在面试或竞赛中，它往往是区分度所在。

8. 背包问题求方案数与具体方案

8.1 求方案数

问题变体：不要求最大价值，而是求装满背包（或容量不超过背包）的总方案数。此时，dp[j]的定义需要改变。我们定义dp[j]为：容量恰好为 j 的背包，装满的方案数。

• 初始化：dp[0] = 1（容量为0的背包，不放任何物品就是一种方案），dp[1...V] = 0。
• 状态转移：对于每件物品 i（以01背包为例），dp[j] += dp[j - w[i]]。意思是，要装满容量 j，可以从装满容量j-w[i]的状态，通过放入物品 i 转移过来。注意这里是累加方案数。
• 遍历顺序：根据物品是01背包还是完全背包，决定内层循环是倒序还是正序。

// 01背包求方案数（装满容量恰好为V） vector<int> dp(V + 1, 0); dp[0] = 1; for (int i = 1; i <= N; ++i) { for (int j = V; j >= w[i]; --j) { dp[j] += dp[j - w[i]]; } } int ans = dp[V];

8.2 求具体方案（输出字典序最小的方案）

有时我们需要知道达到最大价值时，具体选择了哪些物品。这需要在动态规划过程中记录“决策路径”。

常见的方法是使用一个二维数组g[i][j]来记录状态(i, j)是由哪个决策转移过来的。但更优雅且节省空间的做法是：在完成最优值计算后，从最终状态dp[N][V]倒推。

为了便于输出字典序最小的方案，我们可以在动态规划时倒序枚举物品（从 N 到 1）。这样，在倒推找方案时，我们正序（从 1 到 N）判断，就能优先考虑编号小的物品是否被选中。

// 假设已用二维数组 f[N+1][V+1] 计算完最大价值 int i = N, j = V; vector<int> chosen; while (i > 0 && j > 0) { // 如果 f[i][j] 是由 f[i-1][j-w[i]] + v[i] 转移而来，说明选了物品i if (j >= w[i] && f[i][j] == f[i-1][j - w[i]] + v[i]) { chosen.push_back(i); j -= w[i]; } i--; // 无论选没选，都考虑前一个物品 } // 此时 chosen 中存储的是倒序选择的物品编号，反转即可得到正序 reverse(chosen.begin(), chosen.end());

对于字典序最小的要求，只需保证在倒推判断时，对于编号小的物品（在正序循环中先遇到），在“可选可不选”的情况下，优先选择“选”即可。

9. 常见问题排查与实战技巧实录

即使理解了所有原理，实际编码时依然会踩坑。下面是我总结的几个高频问题和技巧。

9.1 为什么我的01背包结果总是偏大？

问题现象：计算出的最大价值比预期大。排查思路：

1. 检查内层循环顺序：这是最常见的原因。确保01背包使用一维数组时，内层循环是**从大到小（倒序）**遍历容量。如果写成了正序，就变成了完全背包，物品会被重复计算。
2. 检查数组越界：在内层循环for (int j = V; j >= w[i]; --j)中，确保j - w[i]不会小于0。虽然循环条件已经限制，但如果w[i]为0或负数（题目不合理），会导致问题。
3. 检查输入数据索引：确保物品的重量w[i]和价值v[i]的索引与循环中的i对应。通常我们会将下标从1开始，方便理解。

9.2 多重背包二进制拆分后，为什么答案不对？

问题现象：使用了二进制拆分，但结果与拆成单个物品的朴素方法不一致。排查思路：

1. 拆分逻辑错误：确保二进制拆分的循环正确。for (int k = 1; k <= num; k *= 2)中，k是每次拆出的系数，num是剩余数量。拆分后要用k * w[i]和k * v[i]作为新物品的重量和价值。
2. 遗漏剩余部分：在k的循环结束后，必须检查num是否还大于0。如果大于0，需要将剩下的num个物品作为一个整体再进行一次01背包。这是很多人遗漏的一步。
3. 容量遍历顺序：拆分后的每个“物品包”应被视为独立的01背包物品，因此处理它们时，容量循环必须是倒序。

9.3 求方案数时，初始化dp[0]=1的含义是什么？

这是一个理解上的关键点。dp[0]=1代表“容量恰好为0的背包，有一种装法：什么都不装”。这是一个合法的、基准的状态。所有其他状态都从这个状态转移而来。

如果题目要求“容量不超过V的方案数”，我们可以在计算完“恰好”为 j 的方案数后，对dp[0...V]求和。或者，也可以改变dp[j]的定义为“容量不超过 j 的方案数”，但转移方程会变得复杂，通常不这么做。

9.4 如何调试复杂的背包DP？

1. 打印DP表：对于二维DP，在每次外层循环结束后打印整个dp数组（或关键几行）。对比手动模拟的结果，可以快速定位状态转移错误发生在哪一步。
2. 小数据量暴力对拍：写一个暴力枚举所有组合的算法，用于测试小数据量（N <= 20）下的结果。用随机生成的小数据反复运行你的DP程序和暴力程序，比对答案。这是竞赛中验证算法正确性的黄金方法。
3. 使用调试器观察变量：在关键行（如状态转移方程dp[j] = max(...)）设置断点，观察j,w[i],dp[j],dp[j-w[i]]等变量的值是否符合预期。

9.5 背包问题的时间与空间复杂度估算

• 时间复杂度：主要看状态数量和每个状态的转移代价。
  • 01/完全背包（一维）：O(N * V)
  • 多重背包（二进制拆分）：O(V * Σlog s[i])
  • 分组背包：O(V * Σ|group_k|)，其中 |group_k| 是第k组的物品数。
  • 二维费用背包：O(N * V * U)
  • 有依赖的背包（树形）：最坏可达 O(N * V^2)，但通常树形结构会限制常数。
• 空间复杂度：一维优化后通常是 O(V) 或 O(V * U)（二维费用）。如果要求输出具体方案，可能需要 O(N * V) 来存储决策信息。

掌握这些复杂度，可以帮助你在面对题目时快速判断算法是否可行，以及如何进行优化。背包问题的学习，是一个从理解模板到灵活应用，再到融会贯通的过程。最好的学习方法，就是在理解这九讲的基础上，去刷大量的相关题目，从“识别这是哪种背包”开始，逐步过渡到处理各种变体和组合。当你看到一个问题能立刻反应出它背后的背包模型时，你就真正掌握了这门“手艺”。