题目描述
选取和不超过 S 的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入格式
输入一个正整数 S。
输出格式
输出最大的约数之和。
输入输出样例
输入 #1复制
11
输出 #1复制
9
说明/提示
【样例说明】
取数字 4 和 6，可以得到最大值 (1+2)+(1+2+3)=9。
【数据规模】
对于 100% 的数据，1≤S≤1000。
#include <bits/stdc++.h>
using namespace std;const int N = 1000;
int dp[N];int f(int n){int s=0;for(int i=1;i<n;i++){if(n%i==0) s+=i;}return s;
}
int main() {int s;cin>>s;for(int i=1;i<=s;i++){for(int j=s;j>=i;j--){dp[j]=max(dp[j],dp[j-i]+f(i));}}cout<<dp[s];return 0;
}f(int n) 函数：用来计算整数 n 的所有真约数（不包括 n 本身）的和
-
外层循环：
i从1到s，表示每次尝试选一个数字。 -
内层循环：
j从s到i，表示对于和为j的情况，是否选择当前的数字i。dp[j]可以通过选择i来更新为dp[j - i] + f(i)，即如果选了数字i，则j - i的最大约数和加上i的约数和。 -
最后，
dp[s]就是选取和为s的数字组合时，所能获得的最大约数和。
