如果只用一个词来形容洛谷P1734这道题我的答案是披着数论外衣的01背包。题面里没有“背包”两个字也没有“物品”“容量”这些字眼但当你把它翻译成动态规划语言之后你会发现它就是最经典的那种每个物品只能用一次的0-1背包模型。很多初学者做这类题时最容易卡住的一步不是不会写状态转移方程而是看不出这是个背包模板背得再熟换了一道名字里完全没有“背包”的题就懵了。我就拿P1734当手术台从题面翻译、模型建立、滚动数组优化到初始化陷阱把01背包从里到外拆一遍。写给你三种人看刚学动态规划、还在背模板的入门者做过不少背包题但总觉得理解不深的半熟手以及想搞清楚“为什么循环要倒着写”的追问型选手。1. 一道披着数论外衣的背包题P1734到底在问什么1.1 题目翻译成人话不同数字、和上限、真约数收益原题大致是这样给定一个正整数n你需要在1到n这些数中挑出若干个不同的正整数让它们的和不超过n然后把这些被选中的数字各自的“约数之和”加起来求这个总收益的最大值。这里的“约数之和”需要特别说明一下它指的是一个数所有的正约数加起来但不包括这个数本身。比如6的约数是1、2、3、6去掉自身之后是12368的约数是1、2、4、8去掉自身之后是1247而1只有约数1去掉自身之后就是0。所以题面翻译成人话就是给你一个容量为n的背包1到n这些数字是候选物品每个数字最多只能选一次选数字i会占用i这么多“容量”同时给你这个数字的真约数和作为收益问容量不超过n时收益最大是多少。听到这里学过背包的人其实已经反应过来了这不就是01背包吗但为什么很多人第一眼看不出来因为题目里没有出现“物品重量”和“物品价值”这种熟悉的词取而代之的是一堆数论概念。1.2 为什么直接枚举和贪心都靠不住先说说最朴素的思路枚举1到n的所有子集检查每个子集的数字和是否不超过n然后算收益取最大值。这个方案对n很小时没问题但n可以到1000子集数量是2的1000次方这个量级连计算机都束手无策所以暴力枚举直接出局。也有人会想到贪心我按“收益/体积”的性价比排序每次优先挑性价比最高的数字行不行这个想法看起来很自然但这个题目并不满足贪心策略所需要的性质。你挑了一个性价比高的数字之后它占用的容量可能会导致后续几个数字的组合放不进去反而错过了一个总收益更高的方案。动态规划的意义就在于它不会只盯着当前这一步的局部最优而是把“容量j时能得到多少收益”这个子问题逐一解决最后用子问题的答案拼出全局最优解。这也是为什么几乎所有背包类问题都要用动态规划而不是贪心来做的根本原因。2. 把“选数字”翻译成01背包物品、体积、价值三个映射2.1 经典01背包状态设计与转移方程回顾先快速回顾一下经典01背包。假设有n个物品第i个物品的体积是w[i]价值是v[i]背包总容量为C每个物品最多拿一次问容量不超过C时能装下的最大价值是多少。我们定义状态dp[j]表示“背包容量为j时能获得的最大价值”然后对每个物品i做一次决策要么不拿它容量j的价值保持不变要么拿它价值变成dp[j-w[i]]v[i]。二者取较大值得到转移方程dp[j] max(dp[j], dp[j-w[i]] v[i])这个方程看起来简单但它背后有一个非常关键的逻辑你计算dp[j]的时候需要用到的是“还没考虑当前物品i”时的dp[j-w[i]]否则就会出现同一个物品被反复选中的问题。这个逻辑后面讲滚动数组时我会展开现在先把模型建好。2.2 三个映射数字即物品数值即容量约数和即价值现在把P1734和经典01背包做一个映射。整个过程核心就三句话01背包中的概念P1734里的对应一句话解释物品编号i数字1到n每个正整数都是一个候选对象物品体积w[i]数字本身的值i选了数字i就占用了i这么多“和”物品价值v[i]数字i的真约数和d[i]选它的收益是约数之和背包容量C题目给定的n所选数字的总和不能超过n这个映射做完之后代码骨架其实就已经出来了外层循环枚举每个数字i内层循环枚举容量j按照01背包的方式更新dp数组。很多人觉得建模难其实难的不是代码而是“把数字当成物品”这个思维转换。一旦你习惯了这种抽象很多看似没有关系的题都会露出背包的底色。2.3 判断“为什么不是完全背包”每个数字只能选一次这里还要回答一个很常见的问题为什么它是01背包而不是完全背包完全背包允许同一个物品被选多次而这道题明确要求“若干个不同的正整数”也就是说数字1只能出现一次数字6也只能出现一次。这正好对应01背包里“每个物品最多选一次”的约束。如果题目改成“可以从1到n中随便取数每次取的数字可以重复只要和不超n”那才是完全背包的模型。所以题面里“不同的正整数”这五个字就是判断背包类型的决定性线索。做动态规划题的时候拿到题面先圈出“每个”“至多一次”“互不相同”这类限制词它们直接告诉你该用01背包、完全背包还是多重背包。3. 预处理真约数和组合AC代码从数学到实现的最后一步3.1 真约数和的计算sqrt枚举与边界处理建模完成之后剩下的问题很直接我们需要提前算出每个数字i的真约数和d[i]然后用01背包跑一遍。计算真约数和有两种常见写法。第一种是朴素的O(n²)循环对每个i枚举1到i-1逐个判断是否是约数n≤1000时这个复杂度完全能接受但写起来不够聪明。第二种是sqrt枚举对每个数i只需要枚举因子j从1到sqrt(i)因为约数都是成对出现的找到一个j的同时也就找到了另一个约数i/j。注意两件事一是不允许把i本身算进去二是当j和i/j相等时不能重复累加。边界上有个容易忽略的点1的真约数和是0它本身可以被选但选它不会带来任何收益只会占用1的容量。后面我们会看到这种“零价值物品”对答案的影响很有意思。3.2 主程序实现一份带注释的C模板计算完d数组之后核心部分就是一个标准的01背包循环。下面是完整的C实现#include bits/stdc.h using namespace std; const int MAXN 1005; int n; int d[MAXN]; // d[i] 表示数字i的真约数和 int dp[MAXN]; // dp[j] 表示容量为j时能获得的最大收益 int main() { cin n; // 1. 预处理每个数字的真约数和 for (int i 1; i n; i) { int sum 0; for (int j 1; 1LL * j * j i; j) { if (i % j 0) { if (j ! i) sum j; int other i / j; if (other ! i other ! j) sum other; } } d[i] sum; } // 2. 01背包核心循环 for (int i 1; i n; i) { // 外层枚举每个数字物品 for (int j n; j i; j--) { // 内层倒序枚举容量 dp[j] max(dp[j], dp[j - i] d[i]); } } cout dp[n] endl; return 0; }注意内层循环我写的上界是j i而不是j 1再判断if (j i)因为当容量j小于物品体积i时这个物品根本放不进去dp[j-i]也没有意义。这样写不仅更简洁还省掉了一部分无用的max比较。3.3 拿n8手工验证一次完整转移纸上模拟一下n8的情况能直观感受到这个流程。先算出d数组数字i12345678真约数和d[i]01131617然后跑01背包最终dp[8]的值是7。这个7的来源有两类一是只选数字8约数和是1247和正好是8二是选数字6和2628收益是617。两条路都达到最大收益7所以答案是7。这个手工验证很重要因为它同时说明了两个容易忽略的事实第一数字n本身也是一个候选物品它可以单独装满整个背包第二最优解完全可能由两个或更多数字组合而成单看某个数字的收益高低并不靠谱。4. 倒序更新不是玄学二维到一维的降维推导与初始化陷阱4.1 先写二维版本把转移方程摆到明面上很多教程直接给你一维写法然后就让你背“倒序遍历”但如果你不理解为什么代码稍一改动就会错得莫名其妙。我们先把二维版本写出来让状态转移的逻辑暴露在阳光下。定义dp[i][j]表示只考虑数字1到i容量为j时能获得的最大收益。那么dp[i][j]只有两种来源不选数字i那么它等于dp[i-1][j]选数字i前提是j i那么等于dp[i-1][j-i] d[i]。取max就是转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-i] d[i])注意右侧两个值都来自“上一轮”也就是只考虑前i-1个数字时的结果。这是01背包最核心的性质每个物品只决策一次当前轮的更新绝不能使用当前轮已经被改过的数据。4.2 滚动数组的降维逻辑为什么j必须从大到小二维版本的空间是O(n²)对这道题来说完全够用但很多进阶题会用更大的n把二维卡爆所以必须掌握滚动数组优化。优化的思路很朴素第i行只依赖第i-1行我们不需要保留所有历史行一个一维数组就能滚动更新。关键点在于更新顺序。如果我们用一维数组dp并且内层循环从n到i倒序更新那么更新dp[j]的时候dp[j-i]还没有被当前第i轮更新过它仍然是上一轮dp[i-1][j-i]的值。这正好满足转移方程对“上一轮数据”的要求。反过来如果内层循环正序从小到大更新就出事了。以n8、数字2为例直观展示一下正序更新时dp[2]先被更新成1然后dp[4]看到dp[2]已经是1于是dp[4]dp[2]12接着dp[6]dp[4]13dp[8]dp[6]14。这个结果相当于把数字2选了4次显然不是01背包的含义。所以“倒序”不是一个需要死记的规则而是为了保证每个物品最多被选一次这个约束不被破坏。4.3 “不超过容量”还是“恰好容量”初始化的一字之差初始化也是背包问题里最阴险的坑之一。dp数组全填0表示“容量j下什么都不放时收益是0”对应的是“所选数字和不超过n”这种非精确约束。这在本题是正确的因为我们允许容量剩余。如果把题目改成“所选数字和恰好等于n”那初始化就要变成dp[0]0、其他位置为负无穷表示只有容量0是合法初始状态其他容量暂时不可达。这个区别在一般背包题里非常致命。举个例子物品体积只有2和3容量为4时“不超过容量”的最优解是选体积2的物品价值假设是5但“恰好装满”时没有合法方案答案应该是不可行而不是5。一字之差整个答案的语义就变了。放到P1734这道题里虽然答案一般不会因为初始化不同而翻天覆地但你如果养成“全0初始化包打天下”的习惯遇到精确约束的题就会踩大坑。我的建议是每次写背包前先问自己一句题目说的是最多不超过容量还是必须恰好达到容量这是比循环顺序更优先要确认的事情。5. 当背包被“换皮”同类问题的识别方法与我常用的判断清单5.1 三道变式题同一背包骨架的不同伪装学会了P1734不能只停留在会做这一道题的层面。我拿几个同样“换皮”的变式题说说建模套路你感受一下。第一道在1到n里选若干个互不相同的数字使它们的和不超过n并且让这些数字的乘积最大。这个题同样可以用01背包只不过价值从加法变成了乘法转移变成dp[j] max(dp[j], dp[j - i] * i)初始化需要把dp数组填成1而不是0因为乘积的“零元”是1。本质还是“每个数字选或不选”的决策。第二道给出一组数字问能否从中选出若干个数使它们的和恰好等于某个目标值T。这是01背包的可行性版本把dp改成布尔数组转移变成dp[j] dp[j] || dp[j - w[i]]。这种考法在“分割等和子集”类的题目中非常常见。第三道把“价值”换成其他函数比如每个数字的质因子个数、因子个数、数字的某种权值然后求容量限制下的最大权值和。你会发现无论权值函数怎么变只要满足“对象互不相同、总量不超过限制、收益可加”这三个特征主流程永远都是那三五行的01背包循环。变的是预处理不变的是骨架。5.2 判断背包问题的五个问题经过这些题之后我总结了一个很实用的判断流程。拿到一道动态规划题先别急着写代码在草稿纸上问自己五个问题是否存在一个“对象集合”每个对象是否最多只能选一次是否存在一个“总量约束”比如和不超过n、重量不超过W、花费不超过预算。优化目标是否能表达成某种收益的累加或累乘如果对象重复选择会改变问题的语义吗决策过程中一个对象的选择是否会影响到其他对象的选择空间如果前三个问答案都是“是”第四个问答案通常是“会改变”第五个问答案是“除了容量占用之外没有额外影响”那这个题十有八九就是背包模型。你只需要把对象、约束、收益分别映射成物品、容量、价值问题就解决了一大半。5.3 真正的分水岭是模型识别能力坦白说背包问题的状态转移方程我见过太多人背得滚瓜烂熟但一到新题就翻车原因几乎都是“看不出这是个背包”。P1734就是一个很好的训练样本它把物品体积和价值用数论函数包装起来容量藏在“和不超过n”这句话里物品个数干脆就等于容量数值本身。你一旦看穿这层包装剩下的代码甚至比许多字符串模拟题还短。我自己做完这类题之后养成了一个习惯无论题目看起来是数论、排列组合还是图论背景只要遇到“从一堆东西里选几个东西限制某种总和求最大收益”这种句式就先往背包上想一遍。这个习惯帮我省下了大量在错误方向上瞎试的时间。最后再分享一个实操小技巧验证背包代码对不对不用急着提交随手设一个很小的n比如n8或n10手工算出一个预期答案再用代码跑。如果手工推的和代码跑的不一致那多半不是逻辑写错就是初始化写错。这个动作虽然简单却能在比赛和练习中帮你省掉一整轮“交上去才发现WA”的返工时间。动态规划这类题纸上推演永远比盯着屏幕发呆有用。