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背包为例不选那么最大价值就等于考虑前 i-1 件物品、容量为 j 时的最大价值即dp[i][j] dp[i-1][j]。选前提是能装下即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]。根据上面的分析核心代码如下vectorvectorint dp(N 1, vectorint(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 所能获得的最大价值。关键代码如下vectorint 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背包的一维转移方程一模一样。唯一的区别就在于内层循环的遍历顺序。完全背包必须正序遍历容量vectorint 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 的四个“新物品”因为 124613。其中1,2,4是2的幂次2^0, 2^1, 2^2最后的6是剩余的数量13-1-2-46。这样通过选或不选这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开始 vectorint 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背包规则为例一维优化后的核心代码注意是两层费用循环且都需要倒序vectorvectorint dp(V 1, vectorint(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 时的最大价值。核心的遍历顺序是三层循环但理解其逻辑至关重要第一层循环遍历每一个组。第二层循环遍历背包容量j必须倒序因为每组内最多选一个类似于01背包。第三层循环遍历当前组内的每一个物品k。关键点在于对于固定的组i和固定的容量j我们遍历组内所有物品k尝试用物品k更新dp[j]。由于容量循环是倒序的保证了组内物品不会重复选取。// 假设有 K 个组每组物品信息存储为 vectors vectorint 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为根的子树的各种可能方案即花费不同容量获得不同价值。处理流程DFS 递归处理先递归处理所有子节点附件得到每个子节点在不同容量下的最优价值即它们各自的dp数组。合并分组将当前主件u视为一个必选物品花费w[u]价值v[u]。然后它的每个子节点附件都对应一组选择方案选或不选该附件以及如果选花多少钱。我们需要将这些子节点的方案与主件进行组合。分组背包决策这个过程实质上是一个分组背包。主件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 vectorint 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[N1][V1] 计算完最大价值 int i N, j V; vectorint 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背包结果总是偏大问题现象计算出的最大价值比预期大。排查思路检查内层循环顺序这是最常见的原因。确保01背包使用一维数组时内层循环是**从大到小倒序**遍历容量。如果写成了正序就变成了完全背包物品会被重复计算。检查数组越界在内层循环for (int j V; j w[i]; --j)中确保j - w[i]不会小于0。虽然循环条件已经限制但如果w[i]为0或负数题目不合理会导致问题。检查输入数据索引确保物品的重量w[i]和价值v[i]的索引与循环中的i对应。通常我们会将下标从1开始方便理解。9.2 多重背包二进制拆分后为什么答案不对问题现象使用了二进制拆分但结果与拆成单个物品的朴素方法不一致。排查思路拆分逻辑错误确保二进制拆分的循环正确。for (int k 1; k num; k * 2)中k是每次拆出的系数num是剩余数量。拆分后要用k * w[i]和k * v[i]作为新物品的重量和价值。遗漏剩余部分在k的循环结束后必须检查num是否还大于0。如果大于0需要将剩下的num个物品作为一个整体再进行一次01背包。这是很多人遗漏的一步。容量遍历顺序拆分后的每个“物品包”应被视为独立的01背包物品因此处理它们时容量循环必须是倒序。9.3 求方案数时初始化dp[0]1的含义是什么这是一个理解上的关键点。dp[0]1代表“容量恰好为0的背包有一种装法什么都不装”。这是一个合法的、基准的状态。所有其他状态都从这个状态转移而来。如果题目要求“容量不超过V的方案数”我们可以在计算完“恰好”为 j 的方案数后对dp[0...V]求和。或者也可以改变dp[j]的定义为“容量不超过 j 的方案数”但转移方程会变得复杂通常不这么做。9.4 如何调试复杂的背包DP打印DP表对于二维DP在每次外层循环结束后打印整个dp数组或关键几行。对比手动模拟的结果可以快速定位状态转移错误发生在哪一步。小数据量暴力对拍写一个暴力枚举所有组合的算法用于测试小数据量N 20下的结果。用随机生成的小数据反复运行你的DP程序和暴力程序比对答案。这是竞赛中验证算法正确性的黄金方法。使用调试器观察变量在关键行如状态转移方程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) 来存储决策信息。掌握这些复杂度可以帮助你在面对题目时快速判断算法是否可行以及如何进行优化。背包问题的学习是一个从理解模板到灵活应用再到融会贯通的过程。最好的学习方法就是在理解这九讲的基础上去刷大量的相关题目从“识别这是哪种背包”开始逐步过渡到处理各种变体和组合。当你看到一个问题能立刻反应出它背后的背包模型时你就真正掌握了这门“手艺”。