在OJ上做P1734“最大约数和”这道题时很多人的第一反应是约数和跟背包有什么关系难道要先把1到S的约数和全算出来再暴力凑组合可等你把题意真正翻译完就会发现这是一道特别典型的动态规划01背包题所有背包要素都在只是把“体积”换成了数字本身把“价值”换成了约数和。用这道题来理解01背包比背十遍模板都有用因为它逼你去想清楚每个物品到底能不能重复选数组为什么要倒着更新状态里存的到底是“恰好”还是“不超过”这篇文章我会从题意开始拆把状态设计、约数和预处理、一维滚动数组的完整实现、常见踩坑点全部过一遍。适合刚学动态规划不久、想找一道题巩固背包模型的人也适合准备竞赛但一直被各种背包变体绕晕的同学。1. 拆开P1734的题面约数和只是“价值”的包装1.1 题目到底在问什么输入的S是一个正整数要求你从1、2、3、……、S这些正整数里选若干个数出来。有两个约束第一选出来的数必须“互不相同”也就是说每个数字最多只能被选一次第二这些选出来的数的总和不能超过S。最后每个被选中的数都会贡献自己的“约数和”作为得分目标是让总得分最大。举个具体例子S4数字1的约数和是1数字2的约数和是123数字3的约数和是134数字4的约数和是1247。如果只选4总和是4刚好不超过S得分7选1和3总和也是4得分145选1和2总和3得分134。所以S4时最优方案就是单选4答案是7。再看S5这个例子特别能说明问题。数字5的约数和是156如果只看单个数字6已经不小了。但选1和4总和5得分178比单选5还大。也就是说不能贪心不能看到某个数“单个价值高”就直接选它必须用背包把所有组合的价值都算出来。1.2 “不同正整数”决定了这是01背包题目里明确要求“若干个不同的正整数”这一点非常关键。每个数字只能出现一次对应01背包中每个物品最多取一次。如果题目改成“可以重复选取同一个数字”那就是完全背包状态转移时容量方向的处理方式完全不同答案也会差很多。我记得刚带某位同学做这道题时他把“每个数只能选一次”理解成了“每种数值可以重复”结果S4的时候他算出答案是10因为他选了两次2约数和336再加1的1总得分7不对他实际上是用了完全背包模板得到了错误结果。后来我让他把选择方案列出来他才发现同一个数字被用了多次这不满足题意。所以看到“不同”两个字第一反应就应该是01背包。还有一点容易被忽略题目要求“和不超过S”不是“恰好等于S”。也就是说背包不需要装满最后dp[S]里存的就是所有容量不超过S的情况中的最大值。这个区别决定初始化方式因为允许不装dp数组全为0就能表示合法状态如果题目要求恰好装满初始化时要让dp[0]0其他dp[j]设为负无穷。1.3 约数和到底包不包括它自己“约数和”这三个字在不同题目里可能有细微差别。有人会下意识认为“约数”不包括自身其实不是。P1734这里的约数和指的是一个数所有正约数之和其中包含1和这个数本身。比如4的正约数是1、2、4所以约数和是7。如果题目想让你求“真约数和”一般会明确说“不包括自身”或者“除自身以外”。比赛时遇到含糊表述看样例能猜出来P1734的样例和常见题解都按包含自身处理。预处理约数和时这个“包含自身”的性质很重要因为它让物品的价值可能大于物品本身的体积。比如2的重量是2价值是3价值比重量还大所以选2往往很划算。但即使如此也不代表我们应该贪心选所有“价值大于重量”的数因为容量有限选了它可能挤掉其他组合。这就是背包问题需要动态规划的根本原因局部最优拼不出全局最优。2. 把P1734翻译成01背包状态、转移、滚动数组2.1 背包三要素在题目里的对应关系标准01背包问题有三个关键概念物品、容量、价值。P1734里这三样东西一开始有点隐蔽但对应关系非常规整背包概念P1734中的对应物品数量数字1到S共S个物品第i个物品的体积数字i本身的大小第i个物品的价值数字i的约数和val[i]背包容量所选数字的总和上限S每个物品的选取次数最多选1次这样一对照问题就清晰了我们有一个容量为S的背包有S个“数字物品”每个数字的体积就是它的编号价值是它的约数和问最大能装多少价值。很多同学会困惑“体积怎么等于编号”这是这类题目的特殊设计但并不影响背包模型。你只需要把每个i当做一个独立的物品它的体积是一个整数i价值是处理好的val[i]就行了。甚至如果题目改成“从2到S里选”也只需要把物品范围换一下。2.2 二维状态定义与转移方程如果不做空间压缩先写二维版本是最容易理解的。设dp[i][j]表示考虑前i个数字也就是数字1到i从它们中选若干个选出的数字总和不超过j时能得到的最大约数和。那么对于数字i有两种决策不选它dp[i][j] dp[i-1][j]选它但前提是j idp[i][j] max(dp[i][j], dp[i-1][j-i] val[i])为什么用dp[i-1][j-i]而不是dp[i][j-i]因为这里要求数字i只能选一次所以必须从“完全没有考虑过数字i”的上一层状态转移过来。如果写成dp[i][j-i]那表示当前数字i已经被选择过再从那个状态继续选就会变成可以重复选择同一数字模型就错了。最终答案是dp[S][S]。二维数组的大小是(S1) x (S1)本题S很小直接开二维也能过。但为了把01背包的理解再往前推一步我建议你直接学会一维滚动数组因为绝大多数背包题的优化套路最后都指向它。2.3 一维数组为什么必须倒序遍历观察二维转移dp[i][]只依赖dp[i-1][]所以可以用一维dp反复覆盖。压缩后状态变成dp[j]表示当前已经处理到某个数字时容量为j的背包能获得的最大价值。伪代码是这个样子for i 1 to S: for j S down to i: dp[j] max(dp[j], dp[j-i] val[i])内层循环必须从大到小也就是“倒序遍历容量”。原因很简单我们希望在计算dp[j]时用到的dp[j-i]还是上一层的旧值而不是已经被当前数字i更新过的新值。如果正序从i到S扫描那么在枚举当前数字i时dp[j-i]可能已经被本轮更新过里面可能已经包含了一次数字i再用它转移就相当于又把数字i放进去一次等于允许数字i被重复选取。用一个最小的例子说明。S2数字1的约数和是1。倒序计算j2时dp[2]max(dp[2], dp[1]1)此时dp[1]还是0所以dp[2]1j1时dp[1]max(dp[1], dp[0]1)得到1。最终dp[2]1正确因为容量2只放一个数字1价值就是1。如果正序j1时dp[1]1j2时dp[2]max(0, dp[1]1)2相当于放入了两个数字1错误。倒序的本质是保证每个物品只被拿一次。生活里类比一下一个背包的检查清单要从后往前打勾才不会被“当前物品已经放进背包”的情况误导。2.4 初始值为什么全为0这里要区分“不超过S”和“恰好装满S”两种问题的初始化差异。P1734要求的是不超过S那么空背包就是一个合法方案价值为0。所以dp数组全部初始化为0没问题dp[0]0顺理成章。如果某道题要求“恰好用完容量S”那么只有容量0是合法起点其他容量初始应该为负无穷表示“无法恰好装满”。因为“不超过”比“恰好”少了限制P1734直接用全0初始化就好这也是背包类题目里最省心的一种情况。3. 完整实现约数和预处理 一维01背包3.1 约数和预处理方式对比在套背包之前必须先把每个数字的约数和算出来。数据范围很小但依然有两种常用做法建议都掌握。方法一试除法对每个i枚举到sqrt(i)如果j是i的约数那么i/j也是i的约数。累加时注意平方数的去重。for (int i 1; i S; i) { for (int j 1; j * j i; j) { if (i % j 0) { val[i] j; if (j * j ! i) { val[i] i / j; } } } }复杂度是O(S sqrt S)。S1000级别时完全没问题。这个方法思路直白适合现场很快写出来。方法二倍数筛法用倍数关系的角度把每个可能的约数d累加到它的所有倍数x上。for (int d 1; d S; d) { for (int x d; x S; x d) { val[x] d; } }比如d1会加到所有数上d2会加到2、4、6……上这样就保证每个x的val里包含了它所有约数d之和。这个写法更短复杂度O(S log S)在S稍大一些时也能跑。两种方法放在一起我更推荐倍数筛因为不容易漏约数也不需要判断平方根去重。3.2 核心AC代码下面给出一份完整的C代码可直接运行#include bits/stdc.h using namespace std; const int MAXN 1005; int val[MAXN]; int dp[MAXN]; int main() { int S; cin S; // 预处理1到S的约数和 for (int d 1; d S; d) { for (int x d; x S; x d) { val[x] d; } } // 01背包一维倒序 for (int i 1; i S; i) { for (int j S; j i; j--) { dp[j] max(dp[j], dp[j - i] val[i]); } } cout dp[S] endl; return 0; }这里有三个细节要提醒。第一外层循环i一定要从1跑到S不要只跑到S-1因为单独选择数字S本身是一个合法且可能最优的方案。第二内层循环从S到i利用了ji这个条件不需要在循环体内再单独判断效率也高。第三dp只需要开S1大小因为容量上限就是S。如果打算用Python思路完全一样S int(input()) val [0] * (S 1) for d in range(1, S 1): for x in range(d, S 1, d): val[x] d dp [0] * (S 1) for i in range(1, S 1): for j in range(S, i - 1, -1): dp[j] max(dp[j], dp[j - i] val[i]) print(dp[S])3.3 手工模拟一遍S4把转移过程看穿很多人写背包题喜欢直接套板子一旦出错就不知道从哪查。我强烈建议你手工模拟一轮小数据比如S4。初始dpdp[0]0, dp[1]0, dp[2]0, dp[3]0, dp[4]0。处理数字1val[1]1j4: dp[4]max(0, dp[3]1)1j3: dp[3]1j2: dp[2]1j1: dp[1]1此时dp[0,1,1,1,1]表示只用数字1时容量至少为1都能得到价值1。处理数字2val[2]3j4: dp[4]max(1, dp[2]3)134表示选数字2和1组合容量3但当前容量4同样得到4j3: dp[3]max(1, dp[1]3)134j2: dp[2]max(1, dp[0]3)3现在dp[0,1,3,4,4]。处理数字3val[3]4j4: dp[4]max(4, dp[1]4)145j3: dp[3]max(4, dp[0]4)4dp[0,1,3,4,5]。容量4下选1和3得5确实比选1和2得4更好。处理数字4val[4]7j4: dp[4]max(5, dp[0]7)7最后dp[4]7和前面手算一致。这个过程能看到每个数字只被考虑一次而且容量方向从高到低所以即使数字4的价值很高它也只能和dp[0]组合不能和已经加入过数字4的状态再组合。3.4 二维转一维是“省内存”但不是“省思考”二维写法更容易验证转移逻辑一维写法代码更短。但一维写法真正考验你的不是代码而是你是否理解“倒序保证不重复”和“覆盖顺序的意义”。如果遇到一道新题不敢确定建议第一遍先写二维跑通之后再压缩成一维。压缩之后如果结果不一致优先检查内层循环是不是倒序。在实际竞赛中空间限制紧张时一维几乎是必须的。P1734虽然二维也能过但养成一维习惯没有坏处。尤其以后遇到二维背包、多重背包你会发现“滚动数组倒序”是贯穿始终的基本功。4. 实战排查P1734和01背包路上的常见坑4.1 内层循环正序把01背包写成了完全背包这是最经典的错误没有之一。症状是代码逻辑看起来没问题但输出偏大而且数字越小越明显。比如S2时预期答案是1却输出2那就是数字1被用了两次。排查方法很简单把内层循环的j改成从S到i倒序再重新跑样例。如果答案恢复正常就说明你踩了这个坑。很多模板题解都强调“倒序”但真正自己写的时候手一滑就写成了for(int ji; jS; j)。我建议在代码注释里直接写明“倒序防重复”。4.2 约数和预处理漏掉平方根去重用试除法算约数和时最常见的bug是对于完全平方数像16j4是它的约数i/j4也是它的约数但它们是同一个数。如果不加if(j*j ! i)17的约数和就会被算成1162844多了一次4最终价值偏大。正确写法是j加入后如果i/j不等于j才再加入i/j。或者干脆用倍数筛从根源上避免这种问题。倍数筛的缺点是稍微有点反直觉但写熟了以后非常稳。4.3 物品范围少枚举了一个S很多人写循环时习惯写for(int i1; iS; i)潜意识里认为“背包容量都是S放进一个体积等于S的物品就没法再装其他东西了是不是没必要”但这不是“没必要”而是可能“最优”。S4时单独放数字4价值7大于任何组合如果不枚举i4答案会变成5。还有一点即使体积等于容量的物品价值不高你也要把它放进物品列表。因为背包问题不要求装满单独放一个体积等于容量的物品可能不是最优但也有可能是是否最优应该交给dp来算而不是在枚举范围上手动排除。4.4 初始化时把dp开成“恰好装满”的负无穷有些同学做上一道“恰好装满”题时用了负无穷初始化到P1734没改回来就会导致dp[S]从负无穷开始状态转移结果可能少一个“什么都不选”的0分支。不过因为最终答案一般会通过选数字得到正值这个问题未必会让答案变错但思路不干净。记住一句话不超过容量dp全0恰好装满dp[0]0其余负无穷。4.5 多组输入或多次运行数组没清空有些题干会隐藏多组数据或者你自己对拍时循环多次运行。val和dp是全局数组上一次运行留下的脏数据会让第二次结果异常。如果要用多组数据每次处理前memset(val, 0, sizeof(val))和memset(dp, 0, sizeof(dp))。用vector定义的话直接重新构造或fill更方便。4.6 用小数据暴力枚举验证DP当你怀疑DP写错了最好的办法不是反复盯代码而是写一个暴力枚举做对拍。对小数据S不超过10可以枚举所有子集int brute(int S) { int ans 0; for (int mask 0; mask (1 S); mask) { int sum 0, score 0; for (int i 1; i S; i) { if (mask (1 (i - 1))) { sum i; score val[i]; } } if (sum S) ans max(ans, score); } return ans; }然后随机生成S分别跑brute和dp比较结果。对拍是排查动态规划错误的好习惯遇到“不知道错在哪”的时候就用小数据暴力兜底。S再小一点手动枚举也行。5. 从P1734里提炼出“一眼看穿01背包”的能力5.1 识别01背包的三个特征做过P1734之后再回头看你会发现它的“马甲”并不厚。所有01背包变体都具备这几个共同点有一组元素每个元素只能使用一次有一个总量限制比如容量、体积、时间、预算要让某个目标值最大化或最小化。只要你从题目里读出“每个物品最多选一次”和“总量不能超过X”就基本可以往01背包方向想。接下来要做的不是急着套模板而是回答三个问题物品是什么每个物品的重量是多少每个物品的价值是多少以P1734为例物品是数字1到S重量是数字本身价值是约数和。把这三个问题写在草稿纸上代码自己就出来了。5.2 为什么不能靠贪心解决有人问P1734里大多数数字的约数和都大于数字本身那我优先选“性价比高”的行不行不行。背包问题里体积和价值是独立的你可能为了一个高价值物品占掉大量容量结果失去了组合出更高总价值的可能性。S5时单选4得7单选5得6但14得8就是一个反例。贪心适合的情况是物品可以分割比如分数背包但01背包的物品不可分割并且每个只能选一次必须枚举所有容量下的最优状态。这也是动态规划在这个问题上不可替代的原因。5.3 常见01背包变体一览以后做题可以自己归类普通背包体积w[i]价值v[i]容量V子集和问题每个数重量等于值价值等于1或者直接判断可行性数字组合问题像P1734一样重量就是数字本身价值是题目额外定义的函数最少物品凑容量容量固定每个物品重量固定求装满所需物品数的最小值其实价值可以等价为1的01背包。识别出变体后核心代码只需要微调重量换一下、价值换一下、目标是max还是min、初始化是0还是负无穷。把这几件事想清楚比刷一百道同类题还有用。5.4 如果题目要求输出选择方案有的扩展题不光要最大值还要输出选了哪些数字。二维做法比较直接转移时用一个choose[i][j]布尔数组记录dp[i][j]这个状态是不是通过选择数字i得到的。最后从dp[S][S]倒着回溯。一维做法也可以另开一个last[j]表示达到dp[j]时最后一次放入的数字然后从S往前追int last[1005]; for (int i 1; i S; i) { for (int j S; j i; j--) { if (dp[j - i] val[i] dp[j]) { dp[j] dp[j - i] val[i]; last[j] i; } } }回溯时注意当前容量j对应的last[j]就是最后一个被放入的数字输出它之后要把容量变成j-last[j]继续看下一个last。这种记录方式在竞赛里很实用但初学阶段可以先不管把最优值搞清楚再扩展。5.5 练熟后你会有什么变化熟练之后再做P1734这种题你会本能地写出一套固定分析流程先看能不能重复再看容量上限然后找价值和体积。这种“建模能力”才是动态规划的核心竞争力。模板只是最后几步的代码落地前期的分析才决定你能不能做对。我自己带人做题时最欣慰的是看到对方不再问“这题为什么用背包”而是能反过来分析“这个题如果改成每个数能用无限次内层循环应该怎么改”。能提出这个问题说明他是真的理解01背包了。最后再分享一个我用到现在的调试习惯看到任何背包题先别急着交手动跑一个S4或S5的例子把dp数组每轮变化写出来确认每一步都符合预期再提交。这个方法虽然笨但能帮你躲过至少一半的写法错误。P1734是一道特别适合练习这个习惯的入门题把它吃透后面遇到再花哨的背包变体你也能一眼看穿。