如果只用一个词来形容洛谷P1734这道题，我的答案是：披着数论外衣的01背包。题面里没有“背包”两个字，也没有“物品”“容量”这些字眼，但当你把它翻译成动态规划语言之后，你会发现它就是最经典的那种每个物品只能用一次的0-1背包模型。很多初学者做这类题时最容易卡住的一步，不是不会写状态转移方程，而是看不出这是个背包：模板背得再熟，换了一道名字里完全没有“背包”的题就懵了。我就拿P1734当手术台，从题面翻译、模型建立、滚动数组优化到初始化陷阱，把01背包从里到外拆一遍。写给你三种人看：刚学动态规划、还在背模板的入门者；做过不少背包题但总觉得理解不深的半熟手；以及想搞清楚“为什么循环要倒着写”的追问型选手。

1. 一道披着数论外衣的背包题：P1734到底在问什么

1.1 题目翻译成人话：不同数字、和上限、真约数收益

原题大致是这样：给定一个正整数n，你需要在1到n这些数中挑出若干个不同的正整数，让它们的和不超过n，然后把这些被选中的数字各自的“约数之和”加起来，求这个总收益的最大值。

这里的“约数之和”需要特别说明一下，它指的是一个数所有的正约数加起来，但不包括这个数本身。比如6的约数是1、2、3、6，去掉自身之后是1+2+3=6；8的约数是1、2、4、8，去掉自身之后是1+2+4=7；而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背包做一个映射。整个过程核心就三句话：

这个映射做完之后，代码骨架其实就已经出来了：外层循环枚举每个数字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 拿n=8手工验证一次完整转移

纸上模拟一下n=8的情况，能直观感受到这个流程。先算出d数组：

然后跑01背包，最终dp[8]的值是7。这个7的来源有两类：一是只选数字8，约数和是1+2+4=7，和正好是8；二是选数字6和2，6+2=8，收益是6+1=7。两条路都达到最大收益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]的值。这正好满足转移方程对“上一轮数据”的要求。

反过来，如果内层循环正序从小到大更新，就出事了。以n=8、数字2为例直观展示一下：正序更新时，dp[2]先被更新成1，然后dp[4]看到dp[2]已经是1，于是dp[4]=dp[2]+1=2，接着dp[6]=dp[4]+1=3，dp[8]=dp[6]+1=4。这个结果相当于把数字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，比如n=8或n=10，手工算出一个预期答案，再用代码跑。如果手工推的和代码跑的不一致，那多半不是逻辑写错就是初始化写错。这个动作虽然简单，却能在比赛和练习中帮你省掉一整轮“交上去才发现WA”的返工时间。动态规划这类题，纸上推演永远比盯着屏幕发呆有用。