企业官网建设流程全解析

动态规划01背包这个模型，在算法竞赛里的出场率极高，但很多人往往只是会背模板，一旦题目换个包装就认不出来了。P1734“最大约数和”就是这样一道典型的“换皮题”：题目描述里既没有“背包”两个字，也没有“物品”和“容量”这些词，但把它想清楚之后你会发现，它就是一个标准的01背包。这篇文章我从题目拆解开始，一步步把状态定义、状态转移方程、约数和的预处理、完整代码以及常见坑全部过一遍，适合刚学完背包模板、正在刷题想巩固理解的人，也适合想弄懂“为什么这题是背包”的人。看完之后，你对01背包的迁移能力应该会提升一个档次。

1. 先搞清楚P1734到底在说什么

1.1 题目还原与直觉分析

P1734题面不长，核心意思大概是：给定一个正整数S，你需要选出若干个不超过S的正整数，使得这些数的和不超过S，并且每个数的约数和（这里约数不包含这个数自身）之和尽量大，输出这个最大值。

关键词有三个：“若干个不超过S的正整数”、“和不超过S”、“约数和（不含本身）”。很多人第一眼看到这题会懵，因为正常人看到“约数和”的第一反应是数学题，谁会想到背包？但如果你坐下来手算几个小数据，就会发现它有很强的“选择”特征。

咱们拿S=6来试。先把1到6每个数的价值（约数和，不含自己）列出来：

• 1的约数没有真约数，价值0
• 2的真约数只有1，价值1
• 3的真约数只有1，价值1
• 4的真约数是1和2，价值3
• 5的真约数只有1，价值1
• 6的真约数是1、2、3，价值6

现在要在总和不超过6的情况下选几个数，让总价值最大。选4和2，价值和正好是6，总价值是3+1=4；选6一个数，总和也是6，总价值是6；选3+2+1，总和6，价值1+1+0=2；选5+1，总和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稍微大一点就完全没法跑。比如S=20已经有一百多万种，S=30就超过十亿了。

再往前走一步，是递归加记忆化。设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”的方案。

我拿S=6的完整转移过程演示一下。初始dp全是0：

看处理物品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]+3=1+3=4，所以变成4。等处理完物品6时，dp[6]=dp[0]+6=6，直接更新成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))。S=1000时没问题，S=10000时有十万级别的运算，也不慢。但如果S加到100000，这个量级就到了几千万次，虽然没有到绝对跑不动的地步，但已经能明显感觉到浪费了，因为你重复计算了大量整除关系。

做算法题养成一个好习惯：当我们需要“所有数的约数和”这种汇总型数据时，先想一步有没有批量产生的办法。答案是有，而且代码很短。

3.2 用倍数法批量计算约数和

思路是这样的：不要站在“每个数有哪些约数”的角度去算，而站在“每个约数应该贡献给哪些数”的角度去算。

外层循环枚举约数i，内层循环枚举i的倍数：2i, 3i, 4i, ...。每碰到一个倍数j，就把i累加到sum[j]里。这样执行完以后，sum[j]里面恰好存了j所有真约数的和。

为什么内层从2i开始？因为题目明确要求“约数不包括自身”。如果从i开始，j第一次就是i本身，会把i自己算进约数和里，那就错了。这一点一定要记牢，它是这个预处理方法里最隐蔽的坑。

拿S=6走一遍：

• i=1：给2、3、4、5、6都加1，表示每个数都有约数1。
• i=2：给4、6加2。
• i=3：给6加3。
• i=4、5：没有倍数在6以内。

最终sum[1]=0，sum[2]=1，sum[3]=1，sum[4]=1+2=3，sum[5]=1，sum[6]=1+2+3=6。和前面手算的完全一致。

这个过程和埃氏筛非常像，都是外层枚举“来源”，内层枚举“倍数”，所以有的地方叫它约数和筛，也有叫调和级数枚举的。不管叫什么都行，关键是理解它的思想：把统计问题从“查表”变成“发消息”。

3.3 预处理代码与复杂度分析

预处理的核心代码只有几行：

vector<int> 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_{i=1}^{S} (S/i - 1) ≈ S * (1 + 1/2 + 1/3 + ... ) - S ≈ S * ln S - S

也就是O(S log S)。这个复杂度在S=100000时大概是一百多万次循环，完全可以在瞬间跑完。相比每个数单独试除的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每个数的约数和（不含自身） vector<int> sum(s + 1, 0); for (int i = 1; i <= s; ++i) { for (int j = i * 2; j <= s; j += i) { sum[j] += i; } } // 01背包 vector<int> 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，所有数都当成一件物品处理。i=1时sum[1]=0，价值为0，它不会对dp造成任何正面影响，所以即使处理它也没关系，反而保持了代码的对称性。

4.2 为什么第二层循环必须倒序

这个点是01背包和完全背包的分水岭，也是初学者最容易写错的地方。第二层循环必须从s递减到i，也就是倒序遍历容量，而不是从i递增到s。

原因说起来其实一句话：为了在更新dp[j]时，保证dp[j-i]还是上一轮（没考虑当前物品时）的旧值，从而保证每个物品最多只用一次。

举个例子。假设S=2，只有一件物品：体积1，价值5。如果第二层循环正序：

• j=1：dp[1] = max(0, dp[0]+5) = 5
• j=2：dp[2] = max(0, dp[1]+5) = 10

你发现没有，dp[2]算出来是10，等于把同一件物品用了两次。因为计算dp[2]时读取的dp[1]已经被刚才那轮更新过了，里面已经包含了当前物品，再叠加上去就重复了。

如果倒序：

• j=2：dp[2] = max(0, dp[1]+5) = 5
• j=1：dp[1] = max(0, dp[0]+5) = 5

计算dp[2]时读到的dp[1]还是上一轮的旧值0，所以结果是5，正确。

这个道理可以类比着理解：正序遍历是从前往后覆盖，新值会污染后续计算；倒序遍历是从后往前更新，每次使用的都是还没被当前物品碰过的干净旧值。只要把这个“污染”模型记住了，以后就不会混淆01背包和完全背包的循环方向了。

4.3 边界情况与初始化细节

几个容易翻车的边界细节，这里一次性说清楚。

第一，dp数组和sum数组的长度都是s+1，下标从0到s。你最终要访问dp[s]，如果数组只开了s长度，就会越界，导致诡异错误。

第二，转移条件j>=i不能省。倒序循环的起点已经是s，当j递减到小于i时，j-i会变成负数，访问dp[负数]直接越界。所以循环条件写成j>=i，从源头堵住这个问题。

第三，s=1时的特殊情况。sum[1]=0，背包循环里i=1，j=1，dp[1] = max(0, dp[0]+0) = 0。输出0，逻辑完全正确。不需要额外特判。

第四，价值非负这个性质很重要。因为所有sum[i]都非负，dp数组必然单调不减，这才有了“输出dp[s]即可”的结论。如果哪天题目把价值改成有正有负，就要重新考虑答案的统计方式了。

5. 做题时的常见问题与排查技巧

5.1 约数和预处理的两个经典错误

这个预处理代码虽然短，但写错的人非常多。第一个错误是把内层循环起点写成j=i而不是j=i*2，导致sum[x]把x自身也算进去了。比如sum[6]会变成1+2+3+6=12而不是6。这种错误不会让程序崩溃，但答案会偏大，而且非常难查，因为思路看起来完全没问题。

第二个错误是为了省一次循环，把外层i从2开始，同时把sum数组初始化为1。这个思路本身可以，因为每个大于1的数的约数都包含1，但容易在细节上翻车：sum[1]也会被初始化成1，但1的真约数和应该是0。如果后面统计答案时正好用到1，就会出错。所以不如老老实实从i=1开始写，内层从2i开始，逻辑最清晰，也不容易出错。

排查这类问题最快的方法是手算小数据。S=6时，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)，等于什么都不做。所以从理论上讲，外层循环从i=2开始也完全没问题，还能省一次循环。

但我更推荐保留i=1。原因有两个：一是代码对称性好，所有物品一视同仁，以后改题目时不容易漏掉；二是这个循环次数是O(S)，在S范围内根本算不上开销。与其花脑力判断“1要不要跳过”，不如统一处理，把注意力放在核心逻辑上。

当然，如果你追求极致严谨，也可以在外层循环前加一行注释说明“sum[1]=0，物品1无价值，可以忽略”。这都不影响正确性，只是风格问题。

5.3 用暴力程序验证你的答案

如果你刚学动态规划，对自己写的状态转移方程不是特别有信心，我强烈建议写一个暴力程序去验证。方法很简单：递归枚举1到S每个数选还是不选，限制总和不超过S，记录最大价值。S比较小时，比如S<=15，暴力的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背包和完全背包的差异彻底焊死在脑子里。