选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
把我们分解出来的因数进行合并，存在一个不知名的数组里，然后我们大可开始我们的迪屁！！（bag），我们可以
把它转化成0 1背包：
f[j]=max(f[j],f[j-1]+sum[i]);
于是：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 5 int f[1001000]; 6 int ans; 7 int n; 8 int sum[1001000]; 9 int main(){ 10 freopen("maxsum.in","r",stdin); 11 freopen("maxsum.out","w",stdout); 12 cin>>n; 13 for(int i=1;i<=n/2;i++){ 14 for(int j=i*2;j<=n;j+=i){ 15 sum[j]+=i; 16 } 17 } 18 for(int i=1;i<=n;i++){ 19 for(int j=n;j>=1;j--){ 20 if(j>=i) 21 f[j]=max(f[j],f[j-i]+sum[i]); 22 ans=max(ans,f[j]); 23 } 24 } 25 cout<<ans; 26 }
大水
原文：https://www.cnblogs.com/WestJackson/p/11372310.html