★ FEATURED ARTICLE 2021年9月2号某大厂秋招笔试一共三题前面两题我做得还算顺第三题卡了我差不多二十分钟。不是不会做而是看到背包问题四个字的时候短暂恍惚了一下——都2021年了笔试还出这么经典的题等真正把题读完才明白经典只是外壳里面塞满了数据范围、变体条件和边界处理。这道题能AC的人大概率不是靠背模板背出来的而是真的把动态规划那套东西吃透了。这篇文章就按我当时的做题思路把这道背包题从读题到AC的完整过程捋一遍二维DP怎么推、一维滚动数组为什么必须倒序遍历、完全背包和恰好装满这类变体怎么改以及笔试现场踩过的真实坑。适合正在准备秋招笔试的同学也适合刷了很多题但总觉得背包问题差点意思的开发者。1. 题目还原背包是外壳动态规划才是本体1.1 题干和数据范围信息量全在数字里经典0-1背包的题干长这样有N件物品和一个容量为V的背包第i件物品重量w[i]、价值v[i]每件物品最多选一次求能装进背包的最大总价值。我遇到的版本是N≤1000、V≤10000、w[i]和v[i]都在int范围内。说实话看到这个数据范围解法基本就锁死了2^N的枚举想都别想O(N×V)的动态规划在10^7量级单组数据一秒内稳过。很多同学拿到题先急着写代码我建议先把数据范围扫一眼因为它直接告诉你该往哪个方向走——就像医生开药前先看化验单范围本身就是提示。还有些题目会追加限定条件比如总重量必须恰好等于V或者物品可以重复选择。这些改动会让裸背包模板当场失效前者要改初始化后者要改遍历方向具体怎么改我在第四节专门展开。1.2 出题人真正想考的三件事这种题放在第三题不是让你默写模板的。复盘的时候我总觉得出题人真正想看的是三件事。第一状态定义能力。dp[i][j]表示前i件物品放进容量为j的背包能获得的最大价值一个定义定乾坤定义错了后面全崩。第二对贪心的免疫力。很多人第一反应是按单位重量价值排序、优先选性价比高的这恰恰是0-1背包最容易栽的思维陷阱。第三空间优化的意识。二维数组1000×10000int占4字节算下来接近40MB笔试环境可能刚好够也可能不够能不能想到压成一维是区分会背模板和真懂原理的分水岭。1.3 贪心为什么在这里必死光说贪心不对没说服力我现场试过构造反例背包容量6三件物品分别是A重量4价值9、B重量3价值6、C重量3价值6。按单位重量价值排序A性价比最高先选A剩余容量2什么都装不下总价值9。但最优解明明是B和C一起装重量刚好6总价值12。贪心拿了9正确答案是12差了三分之一。原因一句话就能讲透背包问题是离散的容量不能切开来用而贪心默认了按比例分配的连续性假设。这也是为什么背包类题目是动态规划最好的入门教材——它逼你接受局部最优不等于全局最优这件事。2. 从选不选到状态转移二维DP推导全过程2.1 先聊聊暴力为什么不可行拿到题第一反应是枚举这很正常。每件物品有选和不选两种状态N件物品就是2^N种组合再对每种组合算重量和价值。N30的时候十亿种组合已经跑不动了更别说题目里N能到1000。暴力的唯一价值是作为正确性验证的基准。我平时自己写题如果DP结果和暴力对不上一定是状态定义或转移写错了而不是怀疑DP本身。2.2 状态定义是怎么想出来的从暴力的视角出发枚举的过程其实是在做N次决策第一件选不选、第二件选不选……每做一个决策手里剩余容量和已获得价值都在变。把决策进行到第i件、当前容量为j这个局面当成一个子问题就得到了状态。更准确地说dp[i][j]定义为只考虑前i件物品、背包容量为j时能获得的最大价值。对最后一件物品做决策第i件要么不选结果就是dp[i-1][j]要么选前提是j ≥ w[i]结果是dp[i-1][j-w[i]] v[i]。两者取最大dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) j ≥ w[i]这就是整个背包问题的核心其余所有优化和变体都是围绕着这一条转移方程在做文章。2.3 用手推一遍比看十遍代码都管用光讲公式太干我拿一个小例子走一遍。背包容量V5三件物品1号重量2价值3、2号重量3价值4、3号重量4价值5。初始化dp[0][j]0意思是0件物品时不管容量多少价值都是0。然后一行一行填。i1时只考虑1号容量0和1放不下价值0容量2到5都能放下dp[1][2..5]3。i2时考虑1号和2号容量2是3容量3取max(3,4)4容量4还是4容量5就是1号和2号都放347。i3时考虑全部三件容量5这里dp[2][5]已经是7而选3号的话是dp[2][1]55两者取max还是7。所以答案dp[3][5]7。注意这个7来自dp[2][5]和dp[2][1]5的对比而不是简单地在之前的答案上叠加——这就是转移方程里max的意义。2.4 复杂度与初始化细节代码框架很简单外层遍历物品内层遍历容量每个状态O(1)转移总复杂度O(N×V)空间O(N×V)。这里有几个新手容易忽略的点。第一j要从0循环到V不能只从w[i]开始因为dp[i][j]在j w[i]时同样需要从dp[i-1][j]继承过来只是不能选第i件而已。第二dp[0][j]0这个初始化不能省它是整个递推的地基。第三如果题目要求的是总重量恰好等于V初始化就不是全0而是负无穷了这个坑在第四节细讲。3. 一维滚动数组倒序遍历不是玄学是数学3.1 二维数组压成一维的依据先看一个关键事实dp[i][j]的转移只依赖dp[i-1][j]和dp[i-1][j-w[i]]也就是只依赖上一行的数据。既然如此二维数组里那些更早的行就都是历史垃圾完全可以扔掉只保留一行不断滚动更新。于是dp变成一维dp[j]表示当前处理完若干件物品后、容量为j时的最大价值。每次迭代用第i件物品去更新这一行dp[j] max(dp[j], dp[j-w[i]] v[i])这里的逻辑是右边的dp[j]是上一轮没考虑第i件时的旧值dp[j-w[i]]也是上一轮的旧值左边的dp[j]是这一轮更新后的新值。问题来了如果用正序循环j那么更新dp[j]时dp[j-w[i]]可能已经在同一次迭代里被更新过了它代表的是已经选过第i件的状态再拿它去更新dp[j]等于第i件被选了两次。3.2 倒序为什么能解决问题反过来如果j从V递减到w[i]更新dp[j]时用到的dp[j-w[i]]因为j-w[i] j而我们是倒着走的这个下标还没被本轮更新过仍然是上一轮的旧值。旧值代表还没选第i件用它转移恰好符合0-1背包每件最多一次的约束。你要是不放心可以手动跑一组小数据容量3一件物品重量1价值2。正序循环dp[1]2dp[2]4等于又选了一次dp[3]6选了三次明显错了。倒序循环dp[3]2、dp[2]2、dp[1]2全部是2正确。跑一遍比背十遍结论都强。3.3 完全背包为什么反而要正序这里有个特别容易搞混的对比如果题目改成完全背包每件物品可以无限选容量循环就必须从w[i]正序到V。因为完全背包本来就不限制选择次数正序允许dp[j-w[i]]在同轮被更新过恰恰实现了重复选一件物品的效果。记住这个对照关系0-1背包倒序完全背包正序。这个相反不是巧合而是动态规划里禁止重复和允许重复的直接体现。笔试如果同时考两种背包这个方向一定不能写反。3.4 笔试可用的模板代码0-1背包一维模板长这样#include bits/stdc.h using namespace std; const int MAXV 10005; int dp[MAXV]; int main() { int n, V; cin n V; vectorint w(n 1), v(n 1); for (int i 1; i n; i) cin w[i] v[i]; 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]); } } cout dp[V] endl; return 0; }注意内层循环的下界是j w[i]小于w[i]的容量根本放不下当前物品直接不更新相当于隐式完成了继承旧值的动作。整段代码跑完dp[V]就是答案。4. 变体与陷阱题目稍微改个条件模板就得跟着改4.1 恰好装满初始化从全0变成负无穷我在笔试里遇到的最隐蔽的坑是题目从不超过容量V改成必须恰好装满V。这两者的DP代码几乎一样唯一区别在初始化恰好装满时dp[0]0dp[1..V]-INF用一个足够小的负数比如-0x3f3f3f3f。原因是容量为0恰好装满是合法且价值为0的状态而其他容量在没放任何物品时不可能恰好装满只能标记为不可达。转移的时候dp[j-w[i]]如果是-INF说明上一个状态不可达那么dp[j-w[i]]v[i]也应当是不可达的这样才不会用一个假状态推出一个假答案。最终如果dp[V]还是-INF说明根本没有方案能恰好装满。我见过不少同学在这类题上栽跟头不是转移写错是初始化没改结果差得离谱。4.2 多重背包二进制拆分把数量摊平如果题目改成第i件物品有c[i]个这就是多重背包。朴素做法是把它当成c[i]件重复的0-1物品但复杂度会变成O(N×V×c)c一大就爆。标准解法是二进制拆分把c[i]个物品拆成1、2、4、8……个捆绑包每个捆绑包在0-1背包里作为一件物品处理。为什么这么拆因为1、2、4、8这些2的幂可以组合出0到c[i]之间的任意数量。比如c13拆成1、2、4、6最后剩的6不是8因为124815已经超过13这四个捆绑包通过选或不选能精确表示拿0到13个的任意情况。拆完之后原问题就退化成了标准0-1背包直接套模板。这个技巧笔试基本必考它是用数学优化暴力的典型代表而且代码量很小背熟很划算。4.3 混合背包的拆解思路还有一种出题方式是一锅炖有的物品只能选一次有的可以无限选有的限定了次数。面对这种混合背包别慌逐类处理只能选一次的用0-1背包的倒序逻辑无限选的用完全背包的正序逻辑限定次数的先二进制拆分再当0-1处理。三种逻辑可以在同一个容量循环里分层实现前提是你对前两节的为什么倒序/正序真的理解到位而不是死记模板。5. 实测翻车记录笔试现场踩过的坑5.1 读题不仔细0-1当成了完全背包这个坑最冤。有一道练习题我上来就按完全背包写正序遍历容量样例全过一交上去大样例WA。后来仔细读题才发现题目写的是每件物品只能使用一次我读题时自动忽略了这句话。从那以后我养成一个习惯拿到题先把每次最多恰好这类限定词圈出来再开始想算法。5.2 int爆精度价值累加要小心背包题里单个v[i]看起来都在int范围内但dp[j]是多个v[i]的累加。N有1000、每件价值接近int上限时总和完全可能爆int。笔试环境里编译器不会提醒你溢出只会给你一个莫名其妙的负数。所以只要题目没明说价值总和在int范围内我建议dp数组一律开long long多花4字节内存换一个稳字。5.3 递归写法好看但笔试里容易翻车有些同学喜欢用记忆化搜索写DP代码确实漂亮但笔试环境有几个隐患一是递归深度N上千的时候递归栈可能爆二是函数调用开销在大数据范围下比循环慢不少三是如果递归里状态设计错了调试起来比循环版本痛苦得多。我的建议是笔试里能用迭代循环就用迭代循环记忆化搜索留给平时学习用。5.4 输入输出的速度也要算进时间N到1000、V到10000数据量其实不大cin/cout一般够用。但如果数据范围再大一个量级或者题目有多组测试数据建议直接上scanf/printf或者关掉iostream同步。这种小细节平时感觉不到笔试时候钟滴滴答答走着能省的时间都是优势。6. 关于这道题我最想说的几句体己话秋招笔试说到底是在有限时间里考察你的肌肉记忆和应变能力。背包问题作为最经典的DP题目几乎每个大厂笔试都会以某种形式出现但每次出现都不完全一样。我复盘这次0902场次的第三题最大的感受是能拿下它的关键不是背了多少模板而是真的理解状态从哪来、转移到哪去、优化为什么成立。我自己的准备方法是把0-1背包、完全背包、多重背包二进制拆分、恰好装满这四种情况各整理成一套不超过20行的模板反复默写到条件反射的程度。平时刷题可以用暴力验证DP正确性但笔试现场直接上优化版本不要给犹豫留时间。最后分享一个小技巧笔试遇到背包题先花30秒确认三件事——物品能不能重复选、容量要不要恰好装满、数据范围允许什么复杂度。这三件事定了代码基本就定了。剩下的就是稳稳地把dp数组填完。
阅读完成 · 觉得有帮助？
