链接：https://www.luogu.org/problemnew/show/P1734
题面：
选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入格式：
输入一个正整数S。
输出格式：
输出最大的约数之和。
样例说明
取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。
数据规模
S<=1000
思路：
把这个数的因数和看成这个数的权值，那么就可以转化成一道01背包了，因为数据非常小，直接暴力预处理出每个数的因数和。
实现代码；
#include<bits/stdc++.h> using namespace std; const int M = 1e5+10; int a[M],dp[M],n; void init(){ for(int i = 1;i <= n;i ++) for(int j = 1;j < i;j ++) if(i%j==0) a[i] += j; } int main() { cin>>n; init(); for(int i = 1;i <= n;i ++){ for(int j = n;j >= i;j --){ dp[j] = max(dp[j],dp[j-i]+a[i]); } } cout<<dp[n]<<endl; }
原文：https://www.cnblogs.com/kls123/p/10845600.html