蓝桥杯必考：背包问题全攻略，从01背包到多重背包

备赛蓝桥杯的同学十有八九会在动态规划这一块碰到背包问题。从历年的真题分布来看背包问题几乎是必考题型而且出题方式特别灵活有的直接考察01背包的板子有的伪装成资源分配问题有的则把完全背包换了个场景包装。很多同学学到一半就卡住了要么是搞不清三种背包之间的区别要么是滚动数组的遍历顺序总记反。这篇文章我会把01背包、完全背包、多重背包一次性说透从状态设计讲到代码实现再到考场上的变形套路和坑点排查帮你真正建立起一套背包问题的解题框架。不管你是刚开始准备蓝桥杯的算法新手还是已经会写基础DP想冲刺省一、国赛的同学都可以按这篇文章的思路走一遍。我会用具体题目和可运行的代码说明每一步都解释“为什么”而不是只丢给你模板。1. 背包问题的战场地位与解题框架1.1 蓝桥杯为什么总爱考背包蓝桥杯的编程题分为填空题和编程大题其中编程大题里动态规划的出场率一直非常高而背包问题正是入门DP最合适的载体。它不像区间DP那样需要复杂的拓扑关系也不像状压DP那样对位运算有要求背包的核心就是一个“选还是不选”的决策过程非常符合DP“状态转移”的基本范式。考背包还有一个现实原因它的难度跨度很大。省赛阶段可能只需要你写出最基础的二维DP国赛阶段就可能要求你结合单调队列或状态压缩来做优化。这就意味着无论你处于备考的哪个阶段背包问题都是性价比极高的复习重点。尤其是蓝桥杯采用OI赛制、有部分测试数据给分的设计哪怕你只会朴素的01背包写法也能拿到相当一部分分数这比很多死磕难题的策略要划算得多。1.2 三要素识别法从题干里捞出背包模型很多同学不是不会写背包而是看不出某道题是背包。我总结了一个“三要素识别法”你用这个方法去审题基本上一抓一个准。第一要素决策。题目里是否存在“拿”或者“不拿”某个东西的抉择。第二要素资源约束。是否存在一个总量限制比如容量、时间、资金、空间。第三要素收益目标。是否需要在约束下最大化/最小化某个值或者求满足约束的方案数。拿一道常见的真题举例有N种饮料每种饮料的体积是v[i]能给到的快乐值是w[i]背包容量是M。问在不超过背包容量的前提下最多能获得多少快乐值。这就是标准的背包模型每种饮料是不是选择拿取对应着“决策”体积对应“资源约束”快乐值对应“收益目标”。一旦你识别出这三要素就成功了大半。接下来只需要判断是哪一种背包如果每件物品只能选一次就是01背包如果每种物品无限拿就是完全背包如果第i种物品只能拿限制的c[i]件就是多重背包。这个分类判断是整个解题过程的起点分类错了后面全歪。2. 01背包一切背包问题的起点2.1 状态设计与二维DP的完整推导01背包问题的描述非常经典有N件物品和一个容量为V的背包第i件物品的体积是v[i]价值是w[i]每件物品只能使用一次求能装入背包的最大总价值。我们一步步设计DP。首先想状态要描述一个决策过程通常需要两个维度一个是已经决策的物品范围另一个是当前背包用了多少容量。于是定义 dp[i][j] 表示“在前 i 件物品中选择放入一个容量为 j 的背包时能获得的最大价值”。关键来了求 dp[i][j] 的时候第 i 件物品只有两种可能的状态。不选第 i 件物品那结果就是前 i-1 件物品在容量 j 下的最优解即 dp[i-1][j]。选第 i 件物品那前提是当前容量 j 至少放得下 v[i]此时背包容量减少了 v[i]价值增加了 w[i]即 dp[i-1][j-v[i]] w[i]。两者取最大值就得到了状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i])这个方程是整个背包家族的核心后面完全背包和多重背包的代码都是从这个方程式上演化出来的。我们用一个具体的例子来跑一遍假设背包容量 V5三件物品的体积和价值分别是 (1, 15), (2, 20), (3, 25)手动推几行DP表格就能看到最优解是45选第2件和第3件总体积5总价值45。二维DP写起来也很直观N和V的范围不太大时可以直接用。#include bits/stdc.h using namespace std; int dp[505][505]; // 根据题目数据范围调整大小 int v[505], w[505]; int main() { int N, V; cin N V; for (int i 1; i N; i) cin v[i] w[i]; for (int i 1; i N; i) { for (int j 0; j V; j) { dp[i][j] dp[i-1][j]; if (j v[i]) { dp[i][j] max(dp[i][j], dp[i-1][j-v[i]] w[i]); } } } cout dp[N][V] endl; return 0; }这里要注意容量的循环范围从0开始遍历如果你从1开始写会漏掉容量恰好等于某件物品体积的情况导致答案偏小。这种细节在外层循环较多时不容易被察觉但一旦碰到某些极限测试数据就会暴露。2.2 滚动数组优化为什么必须逆序遍历二维DP的空间复杂度是 O(N*V)在蓝桥杯题目中如果N达到1000、V达到10000开二维数组会非常吃力。优化思路是观察转移方程dp[i][j] 只依赖 dp[i-1] 这一层的数据那我们就没必要保留完整二维表只用一个一维数组滚动覆盖即可。但这里有一个关键陷阱一维数组在更新时必须逆序遍历容量。原因其实很简单在一维的情况下dp[j] 里保存的是上一轮前 i-1 件物品的结果。正序遍历时当你更新 dp[j] 用到的 dp[j-v[i]] 可能已经在同一轮被更新过了相当于第 i 件物品被使用了多次这恰恰是“完全背包”的行为而不是“01背包”的行为。我换一种更直观的说法逆序时 j 从大到小走dp[j-v[i]] 的位置因为更小还没有被这一轮更新过所以它仍然是“前 i-1 件物品的结果”正好符合01背包“每件物品只用一次”的约束。#include bits/stdc.h using namespace std; int dp[10005]; int v[505], w[505]; int main() { int N, V; cin N V; for (int i 1; i N; i) cin v[i] w[i]; for (int i 1; i N; i) { for (int j V; j v[i]; j--) { dp[j] max(dp[j], dp[j-v[i]] w[i]); } } cout dp[V] endl; return 0; }注意一维数组的优化写法中初始时 dp[j] 全为0代表不放入任何物品时的价值是0。如果你的题目要求“恰好装满”那初始化就要改成 dp[0] 0dp[j] -infj0这个概念我在第5章会详细讲。这段代码需要特别注意循环边界j v[i] 时才有更新意义j 小于 v[i] 的状态不变可以直接跳过。很多优化的写法直接把 j 的起点设成 V这样代码更简洁。2.3 01背包的考场经典考法变化除了“最大化价值”这种最普通的问法01背包在考场上有三个高频率的变形考法我强烈建议你提前熟悉。第一个变体求方案总数。例如给定N件物品和一个背包容量V问恰好装满背包的选择方案有多少种。转移方程从 max 改为求和dp[j] dp[j - v[i]]第二个变体输出选择的物品方案。这个需要在DP过程中另开一个二维路径数组记录当前状态是从哪里转移来的最后逆推找回整个选择序列。由于蓝桥杯很少让你输出具体方案这种考法更多出现在选拔赛和国赛上有兴趣可以往这个方向准备。第三个变体体积和价值互换。有些题目体积很大10^9级别但价值很小这时候你可以把状态定义改成“达到某价值所需的最小体积”然后枚举价值找可行解。这是一种反向思考的技巧在01背包的进阶题目中经常用到。理解了01背包的一维优化再往后的完全背包和多重背包就有了坚实的基础。核心就三句话状态是“前i件物品当前容量”转移是“不选和选两种决策取max”优化的关键是滚动数组覆盖。3. 完全背包把枚举顺序反过来3.1 完全背包和01背包的本质差异完全背包和01背包唯一的区别是每件物品可以无限次使用。别小看这一句话的改变它直接导致了两类背包问题的解法差异甚至很多同学就是从这两个背包的循环顺序开始混淆的。回到状态定义。完全背包同样可以用 dp[i][j] 表示“前 i 种物品放入容量 j 的背包的最大价值”。但转移方程不能简单照搬01背包因为第 i 种物品可以拿0次、1次、2次……直至放不下。如果按照这个思路写就需要在转移时多加一层循环枚举物品的使用件数复杂度会变成 O(NVK)K是每种物品的最大可拿次数在数据较大时很容易超时。数学上可以对这些选择取一个递推我们观察一个关键规律dp[i][j] 和 dp[i][j-v[i]] 之间存在直接联系。dp[i][j-v[i]] 表示“前 i 种物品放入容量 j-v[i] 的背包的最大价值”如果在此基础上再放一个第 i 种物品就得到了容量 j 的一种候选方案。于是完全背包的转移方程也能写成dp[i][j] max(dp[i-1][j], dp[i][j-v[i]] w[i])注意第二项里左上角是 dp[i]不是 dp[i-1]。这跟01背包只差一个下标但意义完全不同dp[i][j-v[i]] 已经考虑了当前第 i 种物品可能被多次使用的情况这正好符合“无限拿”的设定。3.2 一维数组下的正序遍历原理在一维滚动数组的写法中我们需要把容量循环改成正序原因恰恰和01背包相反。正序遍历时当你要更新 dp[j]dp[j-v[i]] 已经被同一轮循环更新过了里面保存的就是“考虑了当前物品可能被使用多次”的状态。这个行为刚好与完全背包的语义吻合。#include bits/stdc.h using namespace std; int dp[10005]; int v[505], w[505]; int main() { int N, V; cin N V; for (int i 1; i N; i) cin v[i] w[i]; for (int i 1; i N; i) { for (int j v[i]; j V; j) { dp[j] max(dp[j], dp[j-v[i]] w[i]); } } cout dp[V] endl; return 0; }这个代码和01背包的代码几乎一模一样唯一区别就是内层循环从正序变成了逆序。我见过太多同学把这两个循环顺序记反结果明明写的是完全背包跑出来却像01背包或者反过来01背包由于正序物品被重复计算导致答案偏大。这里分享一个简单的记忆口诀“01逆序完全正序”。做题前先想清楚自己用的是哪种背包再动笔写内层循环。注意完全背包中“无限使用”不是无限个物品占无限空间而是受限于背包容量。极端情况下如果某件物品体积是1那最多也只能放V件不可能超过程序的运行范围。这也是为什么状态里不需要多一个“已用物品数量”维度的原因。3.3 完全背包的两个高频变形求方案数与最小花费完全背包的变形比01背包还多这里重点说两个最常考的。第一个变形是求方案总数。例如每种物品无限量供应问凑成容量V有几种凑法。这个问题的核心转移是 dp[j] dp[j - v[i]]求组合数时也可以再加一层控制外层物品顺序注意初始化 dp[0] 1表示容量为0时只有一种做法那就是什么都不选。如果题目问的是排列数顺序不同的算不同方案内层和外层循环要反过来这个细节在蓝桥杯的“找零钱方案”和“爬楼梯”题里非常常见。第二个变形是求最小物品数。比如小明要凑到正好金额M每种面额的纸币用多少张不限问他最少需要几张纸币。完全背包的框架可以直接套用只需要把状态更新里的 max 改成 min初始化时把 dp[0] 设为0其余全部设成一个很大的数。用生活化的例子来理解完全背包就像是自助餐厅里你无限续盘但不是每次都要拿同一种菜而是每次选择都基于“当前已经拿过哪些菜”的状态来决策。这个无限续盘的限制不是种类而是你的胃容量。4. 多重背包拆开重组的艺术4.1 朴素做法与复杂度瓶颈在哪多重背包比前两者多了一个约束第 i 种物品最多只能用 c[i] 件。也就是说每种物品既不是1次也不是无限次而是限定了次数。最容易想到的做法是把每种物品的 c[i] 件拆开当成 c[i] 个独立的01背包物品来处理。比如有3件同类的物品就把它们看作3件不同的物品然后跑一个01背包。for (int i 1; i N; i) { for (int k 1; k c[i]; k) { for (int j V; j v[i]; j--) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } } }这份代码能跑但存在一个显著的性能问题。假设有 N1000 种物品每种数量 c[i]10000总拆分数就达到 10^7 级别嵌套后复杂度直接爆掉。蓝桥杯的某些题里数据稍微大一点朴素解法就会超时或超出内存限制。这时候就需要引入多重背包的两个经典优化思路二进制拆分优化和单调队列优化。本文重点讲更通用、更好写的二进制拆分。单调队列优化的推导相对复杂省赛一般用不上我建议先掌握二进制拆分等进入国赛冲刺阶段再学单调队列也不迟。4.2 二进制拆分的原理与模板代码二进制拆分的核心思想是任何一个正整数 c都可以用若干个2的幂次1、2、4、8...加一个剩余数来表示。举个例子c13 可以拆成 1、2、4、6这四个数可以组合出0到13之间的任意整数。这样原本需要13件物品逐个枚举的01背包我们只需处理4件“打包物品”数量从 c 降到了 log2(c) 1。这样做为什么正确因为01背包本质上是在枚举选或不选而任意数量 0~c 的同类物品都可以由这几个打包组组合出来。比如 123代表选3件这类物品246代表选6件。我们不是在枚举每一件具体物品而是把同类物品的多种选取数量“压缩”成组合表达不重不漏地覆盖了所有可能的件数。具体实现上我们先把每种物品按二进制拆分成若干组每一组视为一个新的物品价值 单件价值 * 组内件数体积 单件体积 * 组内件数。拆分完之后问题就转化为一个标准01背包。下面给一份可以直接用的模板代码#include bits/stdc.h using namespace std; struct Node { int v, w; }; vectorNode items; int dp[10005]; int main() { int N, V; cin N V; for (int i 1; i N; i) { int v, w, c; cin v w c; // 二进制拆分 for (int k 1; k c; k 1) { items.push_back({v * k, w * k}); c - k; } if (c 0) items.push_back({v * c, w * c}); } // 01背包模板 for (auto it : items) { for (int j V; j it.v; j--) { dp[j] max(dp[j], dp[j - it.v] it.w); } } cout dp[V] endl; return 0; }注意拆分时的循环条件是 k c每取走一个 k就把 c 减掉 k。循环结束后如果 c 仍大于0余下的部分作为最后一个组。这种写法的好处是不需要额外记录剩余数量代码简洁也不容易出错。我手算一个例子方便你理解c10。拆分过程是先取 k1c 变为9再取 k2c 变为7再取 k4c 变为3此时 k8 大于 c3循环退出剩余 c3 作为最后一个组。最终拆成 1、2、4、3 四组刚好可以组合出0到10之间的任意整数。你随便抽一个数检验无论是514还是624还是7124还是8134都能被拼出来这就是二进制组合的完备性。4.3 单调队列优化知道思路即可二进制拆分后的复杂度是 O(V * N * logC)其中C是单种物品最大数量。如果C特别大比如60000以上logC大约是16再乘上V10000复杂度也可以接受。但如果V也很大、N也很大那可能还得用单调队列优化。多重背包的单调队列优化本质上是对同余类做滑动窗口最大值推导起来比较繁琐我不建议在省赛阶段花太多时间。你需要做的是把二进制拆分写快、写对并知道多重背包还有更快的优化空间即可。5. 背包模型的考场变体与常见套路5.1 恰好装满与“价值最大”的初始化细节对比背包问题中有一个非常容易踩坑的细节同样是求最大价值但“恰好装满背包”和“不需要装满”的初始化方法是不同的。不要求装满dp 数组全部初始化为0。因为任何容量下我都可以“不装任何物品”得到的价值是0这总是一个合法方案。要求恰好装满dp[0] 0其余 dp[j] 初始化成负无穷如 -1e9。负无穷的含义是“当前容量状态不可达”只有从容量0开始逐步添加物品才能到达其他容量。我见过很多同学在“恰好装满”的题目里用了全0初始化结果答案总是比真实值大因为状态里出现了“未装满但被当作装满”的非法解。做题前先看清楚题目描述里有没有“恰好”“正好”这类词。题目条件dp初始化状态含义不超过容量dp[j] 0全0只要不超过容量就合法恰好装满dp[0] 0dp[j] -inf必须恰好达到容量才合法5.2 求方案数与最小物品数除了最大价值背包问题还能求方案数和最小物品数。方案数的转移本质上把 max 换成了求和但要注意初始化dp[0] 1容量为0时有且仅有1种方案即什么都不选其他位置为0。如果求的是组合数不同顺序算同一种方案那么外层循环物品、内层循环容量如果求的是排列数顺序不同的算不同方案那么外层循环容量、内层循环物品。这两个方向我在前面的完全背包部分已经提过这里再重复强调一次因为它们是真的很容易搞混。最小物品数的思路则更像最短路把每件物品看成一次“花费体积换价值”的边状态记录的是达到某容量所需的最少物品数。dp[0] 0其他初始为极大值更新时取 min。5.3 二维费用背包与分组背包二维费用背包指的是物品不仅有体积限制还有另一个限制条件比如重量上限。解决办法是把状态维度从一维扩展到二维dp[j][k] 表示“体积不超过j且重量不超过k”时的最大价值。转移时两层容量循环都要同步更新。分组背包则是把物品分成若干组每组最多选一件。这种问题需要按组为单位处理外层循环是组号中间循环是容量内层循环组内的每个物品。之所以要在“每组内部”循环物品是为了保证同组物品最多只能取一个。核心代码如下for 每组: for j V - 0: for 每个物品 in 这组: dp[j] max(dp[j], dp[j - v[物品]] w[物品]);5.4 考场快速估算复杂度的方法蓝桥杯的编程大题通常限制在2秒左右C的运算能力大约每秒能跑1e8次简单操作Java和Python会慢很多。拿到题目后你先估算自己算法的复杂度如果是O(NV)N和V都在1000量级那没问题如果NV达到1e7~1e8C可以硬跑Python则可能要优化如果达到1e9基本上注定超时需要换思路或者上二进制拆分/滚动数组等优化。用这个估算方法你可以在写代码前就判断方案的可行性省下大量调试时间。6. 实测踩坑记录与调试指南6.1 最常见的四个错误现场我在备考和带新人debug的过程中见到的背包代码错误高度集中在四个地方。第一是数组越界。不少同学把 dp 数组开成 dp[N1][V1]但循环里访问到了 dp[j-v[i]]其中 j-v[i] 可能是负数导致数组越界。最好的规避办法是统一写成“if (j v[i]) 再更新”或者在循环条件里直接写成 j v[i]。用一维数组时尤其要注意这一点。第二是循环顺序反了。01背包和完全背包就差一个循环方向如果你把完全背包的代码写成逆序结果会退化成01背包反过来01背包写成正序物品会被重复使用。这里我提供两个自查方法第一用肉眼检查内层循环的方向第二构造一个只有单件物品的测试数据看结果是否符合预期。第三是状态初始化错误。该用 -inf 的地方用了0特别是“恰好装满”类的问题表现是样例能过但一旦测试数据里出现不可达容量就全错。第四是多重背包的拆分剩余部分没处理好。很多人拆分时只拆2的幂忘了最后给剩余数量补一组导致某些数量无法组合出来答案偏小。我在前面的模板里给了 c - k 的写法这样最不容易漏。6.2 调试技巧对拍与打印DP表调试背包问题最直接的办法是打印DP表。拿一个小规模数据比如3件物品背包容量5把整个dp数组逐行打出来对照手动推导的结果通常一眼就能发现状态是从哪里转移错的。第二个常用技巧是对拍写一个保证正确的暴力解法直接枚举所有方案和一个优化解法用随机小数据反复比对。一旦两边输出不一致就把数据规模缩小逐步定位是哪个状态转移出了问题。这个方法在备战阶段用特别多因为很多边界错误不是肉眼可以轻易发现的。对拍脚本不需要很复杂一个随机数生成器加一个循环比较即可。第三种调试方式是边界特判。手动测试三个边界case背包容量为0时是否正确只有一件物品但体积超过容量时是否正确物品数量为0时是否正确。这三个case通过后基础框架基本没问题再去排查更复杂的逻辑。6.3 备赛复习路线建议背包问题不是一次就能完全掌握的建议按“三轮复习法”来安排时间。第一轮先把三种背包的模板代码各写三遍以上直到能闭着眼睛不查资料默写出来第二轮集中做蓝桥杯历年真题把每道比较难的题目归类为01背包、完全背包、多重背包的哪一类再分析它考了哪一种变形第三轮冲刺阶段再去补进阶技巧比如单调队列优化、数组滚动、路径输出等。如果你是在校备赛我建议给自己制定一个小目标每天做1~2道背包相关题目一周下来就能基本掌握这类题的套路。写在最后我个人备赛时最大的体会是背包问题不像很多算法一样需要聪明的直觉它更考验的是你对状态定义的清晰程度和循环边界的细心程度。你把01背包彻底吃透了完全背包和多重背包都是在此基础上加一点点变化反过来如果你直接去背完全背包、多重背包的模板却不理解一维数组为何要正序、二进制拆分为何能覆盖全部数量那题目一旦变形你又会懵。最后再分享一个实用小技巧把三种背包的模板代码集中放在一个压缩包里考前快速过一遍循环方向和初始化方式。别看这些小细节它们直接决定了你能不能拿稳一道DP大题的分数。