动态规划01背包这个模型在算法竞赛里的出场率极高但很多人往往只是会背模板一旦题目换个包装就认不出来了。P1734“最大约数和”就是这样一道典型的“换皮题”题目描述里既没有“背包”两个字也没有“物品”和“容量”这些词但把它想清楚之后你会发现它就是一个标准的01背包。这篇文章我从题目拆解开始一步步把状态定义、状态转移方程、约数和的预处理、完整代码以及常见坑全部过一遍适合刚学完背包模板、正在刷题想巩固理解的人也适合想弄懂“为什么这题是背包”的人。看完之后你对01背包的迁移能力应该会提升一个档次。1. 先搞清楚P1734到底在说什么1.1 题目还原与直觉分析P1734题面不长核心意思大概是给定一个正整数S你需要选出若干个不超过S的正整数使得这些数的和不超过S并且每个数的约数和这里约数不包含这个数自身之和尽量大输出这个最大值。关键词有三个“若干个不超过S的正整数”、“和不超过S”、“约数和不含本身”。很多人第一眼看到这题会懵因为正常人看到“约数和”的第一反应是数学题谁会想到背包但如果你坐下来手算几个小数据就会发现它有很强的“选择”特征。咱们拿S6来试。先把1到6每个数的价值约数和不含自己列出来1的约数没有真约数价值02的真约数只有1价值13的真约数只有1价值14的真约数是1和2价值35的真约数只有1价值16的真约数是1、2、3价值6现在要在总和不超过6的情况下选几个数让总价值最大。选4和2价值和正好是6总价值是314选6一个数总和也是6总价值是6选321总和6价值1102选51总和6价值1。比较下来最优就是选6答案是6。从这个小例子能看出两个信息第一并不是“选的数越多越好”因为每个数都有体积成本第二也不是“价值最大的数一定最优”因为还要考虑占用空间。这种“在有限资源下做选择使目标最大”的结构就是背包问题最典型的味道。1.2 为什么它本质上就是01背包用背包的语言重新描述一下把1到S之间的每个正整数i都看成一件物品每件物品的体积就是i本身价值就是i的约数和不含自身背包的总容量是S。每个数只能用一次所以是01背包。这么一对照题目里的所有要素都对齐了物品1, 2, 3, ..., S体积物品编号本身价值约数和不含自身背包容量S每个物品只能选一次01背包有些同学可能会纠结1到S每个数是不是都能选当然能题目就说了“不超过S的正整数”。那为什么不会选1因为1的体积是1价值是0选它纯属浪费空间。但它在模型里仍然是一件合法物品只是价值为0不影响结果。这一步“把题目翻译成背包模型”是整个解题过程中最关键的一步。我见过不少同学能把01背包模板背得滚瓜烂熟但一到这种题就卡住了原因就是他们习惯等题目里直接给出“物品体积数组”和“价值数组”而不是自己去造。这道题恰恰需要你自己把这两样东西构造出来。1.3 从暴力枚举到动态规划的思维路径如果不考虑效率最朴素的思路是枚举所有子集。每个数选或不选总共2^S种情况S稍微大一点就完全没法跑。比如S20已经有一百多万种S30就超过十亿了。再往前走一步是递归加记忆化。设f(i, j)表示“考虑前i个数剩余容量为j时能获得的最大价值”那么对第i个数有两个选择不选f(i-1, j)选前提是j i此时为f(i-1, j-i) value[i]。取两者最大值。这个递归带上记忆化其实就是自顶向下的动态规划。把递归改成循环自底向上填表就成了经典的二维DP。二维DP再进一步优化把物品维度压缩掉只保留容量维度就是大家熟悉的滚动数组写法。为什么能压缩因为处理第i个物品时只需要上一轮的结果更早的结果没用了。这个“从暴力到递归再到递推再到滚动数组”的演进过程比直接背模板重要得多。你理解了这条线后面遇到分组背包、二维费用背包、混合背包时都知道它们是怎么从同一个母体变形出来的。2. 状态设计与状态转移方程2.1 dp[j]到底代表什么在处理背包问题时状态定义永远是第一步。这道题我们用一维数组dp[j]表示“当前已经考虑完一部分物品后容量为j的背包能装下的最大价值”。注意下标j是容量不是物品数量。很多初学者会在这里犯迷糊总想着dp[i]表示“选i个数的最优价值”那方向就偏了。因为这里真正受限制的是“总和不超过S”也就是容量而不是数量。我们以容量为维度做DP所有状态都能覆盖。那物品维度去哪了被滚动循环取代了。外层循环每处理一个物品dp数组就更新一次。处理完第2个物品后dp[j]表示“考虑完前2个物品容量j能装下的最大值”处理完第3个后就变成“考虑完前3个物品”。所以一维dp数组的正确理解是它永远表示“处理到当前物品为止”的状态只不过旧状态会被新状态覆盖。2.2 状态转移方程是怎么来的对第i个物品我们要做决策。dp[j] max(dp[j], dp[j-i] sum[i])其中sum[i]是i的约数和不含自身。这个方程拆开看不选第i个物品当前容量j的价值保持原样还是dp[j]。选第i个物品需要腾出i的容量那么剩下j-i的容量能装的价值是dp[j-i]再加上新物品的价值sum[i]总共是dp[j-i] sum[i]。取这两种方案的最大值。为什么可以直接从dp[j-i]转移因为dp[j-i]是上一轮计算好的、还没考虑当前物品时的最优值。它代表了“用其他物品装满j-i容量能获得的最大价值”在这个基础上加入当前物品就自然得到了“包含当前物品且总容量为j”的方案。我拿S6的完整转移过程演示一下。初始dp全是0处理完的物品dp[1]dp[2]dp[3]dp[4]dp[5]dp[6]初始000000物品1体积1价值0000000物品2体积2价值1011111物品3体积3价值1011122物品4体积4价值3011334物品5体积5价值1011334物品6体积6价值6011336看处理物品4那一行。在没考虑物品4之前dp[4]1代表容量4装一个2价值1。现在物品4的价值是3体积正好是4于是dp[4]变成max(1, dp[0]3)3。再看dp[6]本来容量6可以装2和3价值2现在可以考虑dp[2]3134所以变成4。等处理完物品6时dp[6]dp[0]66直接更新成6。这张表走完你会发现每个状态都不是凭空来的都是从上一步的某个旧状态“加一件物品”得到的。这就是动态规划里“递推”二字的含义。2.3 答案到底是dp[S]还是所有dp的最大值这个问题我当年也纠结过。题目要求“和不超过S”没说“恰好等于S”那是不是要输出max(dp[1], dp[2], ..., dp[S])不用。我们初始化dp数组全部为0这个初始化的含义就是容量为j的背包可以什么都不装所以容量j这个状态从一开始就是合法的。换句话说dp[j]天然就表示“容量不超过j”时能拿到的最大价值而不是“恰好装满j”。因为所有物品的价值都非负容量越大能装的东西只会更多不会更少所以dp数组一定是非递减的。既然dp[S]已经是所有前缀状态里的最大值直接输出dp[S]就是答案。如果你把初始化改成dp[0]0、其余为负无穷那含义就变成了“必须恰好装满容量”这时才需要去所有dp[j]里找最大值。很多题会故意用“恰好装满”来恶心人理解了初始化这层含义你就不会被绕进去。3. 约数和的预处理绕过超时的关键一环3.1 朴素暴力的复杂度陷阱题目里的价值是“约数和不含自身”所以第一步必须把1到S每个数的约数和算出来。最直接的想法是对每个数i枚举从1到i/2看哪些能被整除累加。再聪明一点枚举到sqrt(i)然后成对处理约数。这两种写法都能算出正确结果但复杂度不太好看。如果每个数都单独试除复杂度大约是O(S sqrt(S))。S1000时没问题S10000时有十万级别的运算也不慢。但如果S加到100000这个量级就到了几千万次虽然没有到绝对跑不动的地步但已经能明显感觉到浪费了因为你重复计算了大量整除关系。做算法题养成一个好习惯当我们需要“所有数的约数和”这种汇总型数据时先想一步有没有批量产生的办法。答案是有而且代码很短。3.2 用倍数法批量计算约数和思路是这样的不要站在“每个数有哪些约数”的角度去算而站在“每个约数应该贡献给哪些数”的角度去算。外层循环枚举约数i内层循环枚举i的倍数2i, 3i, 4i, ...。每碰到一个倍数j就把i累加到sum[j]里。这样执行完以后sum[j]里面恰好存了j所有真约数的和。为什么内层从2i开始因为题目明确要求“约数不包括自身”。如果从i开始j第一次就是i本身会把i自己算进约数和里那就错了。这一点一定要记牢它是这个预处理方法里最隐蔽的坑。拿S6走一遍i1给2、3、4、5、6都加1表示每个数都有约数1。i2给4、6加2。i3给6加3。i4、5没有倍数在6以内。最终sum[1]0sum[2]1sum[3]1sum[4]123sum[5]1sum[6]1236。和前面手算的完全一致。这个过程和埃氏筛非常像都是外层枚举“来源”内层枚举“倍数”所以有的地方叫它约数和筛也有叫调和级数枚举的。不管叫什么都行关键是理解它的思想把统计问题从“查表”变成“发消息”。3.3 预处理代码与复杂度分析预处理的核心代码只有几行vectorint sum(s 1, 0); for (int i 1; i s; i) { for (int j i * 2; j s; j i) { sum[j] i; } }注意内层循环j的起始值用i*2而不是i。这样写sum[1]会一直保持0符合“1没有真约数”的实际情况。复杂度方面内层循环的总执行次数大约是sum_{i1}^{S} (S/i - 1) ≈ S * (1 1/2 1/3 ... ) - S ≈ S * ln S - S也就是O(S log S)。这个复杂度在S100000时大概是一百多万次循环完全可以在瞬间跑完。相比每个数单独试除的O(S sqrt(S))优势非常明显。很多题解喜欢把这个预处理叫做“类似筛法”我认为这个说法很形象。你在写代码时可以这样理解每个i是个小广播员它向自己的所有倍数广播“我是你的约数价值i”收到广播的数把自己的sum加上i。广播完了所有数的约数和也就齐了。4. 完整解题代码与关键细节4.1 完整AC代码预处理做完剩下的就是标准的01背包。完整代码如下#include iostream #include vector #include algorithm using namespace std; int main() { int s; cin s; // 预处理1到s每个数的约数和不含自身 vectorint sum(s 1, 0); for (int i 1; i s; i) { for (int j i * 2; j s; j i) { sum[j] i; } } // 01背包 vectorint dp(s 1, 0); for (int i 1; i s; i) { for (int j s; j i; --j) { dp[j] max(dp[j], dp[j - i] sum[i]); } } cout dp[s] endl; return 0; }如果你用的环境允许也可以把iostream、vector、algorithm合并成bits/stdc.h但我个人建议还是分开写养成好习惯避免在某些严格环境下编译报错。背包部分的外层循环从1到S所有数都当成一件物品处理。i1时sum[1]0价值为0它不会对dp造成任何正面影响所以即使处理它也没关系反而保持了代码的对称性。4.2 为什么第二层循环必须倒序这个点是01背包和完全背包的分水岭也是初学者最容易写错的地方。第二层循环必须从s递减到i也就是倒序遍历容量而不是从i递增到s。原因说起来其实一句话为了在更新dp[j]时保证dp[j-i]还是上一轮没考虑当前物品时的旧值从而保证每个物品最多只用一次。举个例子。假设S2只有一件物品体积1价值5。如果第二层循环正序j1dp[1] max(0, dp[0]5) 5j2dp[2] max(0, dp[1]5) 10你发现没有dp[2]算出来是10等于把同一件物品用了两次。因为计算dp[2]时读取的dp[1]已经被刚才那轮更新过了里面已经包含了当前物品再叠加上去就重复了。如果倒序j2dp[2] max(0, dp[1]5) 5j1dp[1] max(0, dp[0]5) 5计算dp[2]时读到的dp[1]还是上一轮的旧值0所以结果是5正确。这个道理可以类比着理解正序遍历是从前往后覆盖新值会污染后续计算倒序遍历是从后往前更新每次使用的都是还没被当前物品碰过的干净旧值。只要把这个“污染”模型记住了以后就不会混淆01背包和完全背包的循环方向了。4.3 边界情况与初始化细节几个容易翻车的边界细节这里一次性说清楚。第一dp数组和sum数组的长度都是s1下标从0到s。你最终要访问dp[s]如果数组只开了s长度就会越界导致诡异错误。第二转移条件ji不能省。倒序循环的起点已经是s当j递减到小于i时j-i会变成负数访问dp[负数]直接越界。所以循环条件写成ji从源头堵住这个问题。第三s1时的特殊情况。sum[1]0背包循环里i1j1dp[1] max(0, dp[0]0) 0。输出0逻辑完全正确。不需要额外特判。第四价值非负这个性质很重要。因为所有sum[i]都非负dp数组必然单调不减这才有了“输出dp[s]即可”的结论。如果哪天题目把价值改成有正有负就要重新考虑答案的统计方式了。5. 做题时的常见问题与排查技巧5.1 约数和预处理的两个经典错误这个预处理代码虽然短但写错的人非常多。第一个错误是把内层循环起点写成ji而不是ji*2导致sum[x]把x自身也算进去了。比如sum[6]会变成123612而不是6。这种错误不会让程序崩溃但答案会偏大而且非常难查因为思路看起来完全没问题。第二个错误是为了省一次循环把外层i从2开始同时把sum数组初始化为1。这个思路本身可以因为每个大于1的数的约数都包含1但容易在细节上翻车sum[1]也会被初始化成1但1的真约数和应该是0。如果后面统计答案时正好用到1就会出错。所以不如老老实实从i1开始写内层从2i开始逻辑最清晰也不容易出错。排查这类问题最快的方法是手算小数据。S6时sum数组应该是0, 0, 1, 1, 3, 1, 6。如果你算出来的sum[6]不是6去检查是不是把自身加进去了如果sum[2]是0去检查是不是少加了约数1。5.2 为什么物品1要不要处理都行物品1的体积是1价值sum[1]0。在背包循环里它每一轮更新dp[j] max(dp[j], dp[j-1]0)等于什么都不做。所以从理论上讲外层循环从i2开始也完全没问题还能省一次循环。但我更推荐保留i1。原因有两个一是代码对称性好所有物品一视同仁以后改题目时不容易漏掉二是这个循环次数是O(S)在S范围内根本算不上开销。与其花脑力判断“1要不要跳过”不如统一处理把注意力放在核心逻辑上。当然如果你追求极致严谨也可以在外层循环前加一行注释说明“sum[1]0物品1无价值可以忽略”。这都不影响正确性只是风格问题。5.3 用暴力程序验证你的答案如果你刚学动态规划对自己写的状态转移方程不是特别有信心我强烈建议写一个暴力程序去验证。方法很简单递归枚举1到S每个数选还是不选限制总和不超过S记录最大价值。S比较小时比如S15暴力的2^15种情况瞬间跑完。暴力代码的思路大概长这样int dfs(int idx, int remain) { if (idx s) return 0; int ans dfs(idx 1, remain); // 不选idx if (remain idx) { ans max(ans, dfs(idx 1, remain - idx) sum[idx]); // 选idx } return ans; }然后把暴力的结果和背包代码的结果对比。如果S从1到15所有值都一致那你基本可以放心了。这一步对学习的价值非常大因为很多时候你写着写着就把“选一个物品”和“物品可重复”搞混了暴力程序能在几分钟内帮你把错误暴露出来。5.4 我的几个实战心得做多了这类“换皮背包”题之后我总结出几个规律分享给你。第一遇到“在某种限制下选择若干元素使某个目标最大化”的题第一时间往背包模型上靠。限制条件往往是容量元素个数是物品数量每个元素消耗的资源是体积目标值是价值。第二预处理要主动想“批量”方案。这道题如果没有倍数法意识直接用试除法也能过因为S范围小。但它给你传达了一个信号很多题的预处理复杂度决定了整个题目能不能跑过。养成用调和级数枚举处理“所有数的因子或倍数关系”的习惯以后做因数相关题会非常顺手。第三倒序循环不是死记硬背而是真的理解了“旧值污染”之后自然能写对。如果你总是忘记方向可以每次写代码前小声念一遍“01倒序完全正序。”念多了就不会错了。第四这道题做完后值得再做一个小实验把“每个数只能用一次”改成“每个数可以用任意多次”也就是把01背包改成完全背包你会发现只需要把第二层循环改成正序其他一字不动。这个实验能帮你把01背包和完全背包的差异彻底焊死在脑子里。