最大约数和？

Question

写一个程序  

最大约数和

题目概述：选区和不超过S的若干个不同的正整数，使得所有数的约数（不含他本身）之和最大

输入格式：输出最大的约数之和

输入样例：11

输出结果：9

数据规模:S<=1000

Answer 1

 #include<iostream> #include<math.h> using namespace std; int a[1001],s[1001],n,maxs=0; int ys(int x) {int i,s=0; for(i=1;i<x;i++)    if(x%i==0)s+=i; return s; } void work() {int i; for(i=2;i<=n;i++) s[i]=ys(i); } void dp() {memset(a,0,sizeof(a)); int i,j; for(i=2;i<=n;i++) for(j=0;j<=n-i;j++) a[i+j]=max(a[i+j],a[j]+s[i]); for(i=1;i<=n;i++) if(a[i]>maxs)maxs=a[i]; } int main(){    cin>>n;    work();    dp();    cout<<maxs;    return 0;  }

Answer 2

你孬，0/1背包和最大约数和是不同的动态规划，状态转移方程都不一样怎么用背包做！！！ 下面各你一个标准的程序：