选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入一个正整数S。
输出最大的约数之和。
11
9
样例说明
取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。
数据规模
S<=1000
第一眼看到这个题目的有点蒙，，没思路，，百度了一下，，，原来这么简单。
思路：简单的01背包问题，先构造一个数组里面存有每个数x的约数和，然后约束和为价值，，对应的数字为体积，，总数s为背包容积，，，简单01背包问题。。唉！！
#include<iostream> using namespace std; typedef long long ll; ll arr[1000+10]; ll dp[1000+10]; ll ysh(int x){ int sum=0; for(int i=1;i<x;i++){ if(x%i==0) sum+=i; } return sum; } int main(){ int s; cin>>s; for(int i=1;i<s;i++){ arr[i]=ysh(i); } for(int i=1;i<s;i++) for(int j=s;j>=i;j--) dp[j]=max(dp[j],dp[j-i]+arr[i]); cout<<dp[s]<<endl; return 0; }
反思：：遇到背包问题时有，一定要仔细考虑谁是价值谁知体积。
原文：https://www.cnblogs.com/Accepting/p/11291191.html