c++最大约数和

来源：百度知道 编辑：UC知道 时间：2024/07/08 12:28:17
Problem 3 : maxsum
最大约数和

问题描述
选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入数据
输入一个正整数S。

输出数据
输出最大的约数之和。

样例输入
11

样例输出
9

样例说明
取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。

看我的程序，(⊙⊙?)怎么了？
# include<cstdio>
int max(int a,int b)
{if(a>b)return a;
else return b;
}
main()
{freopen("typewrt.in","r",stdin);
freopen("typewrt.out","w",stdout);
int i,j,a[1001],f[1001]={0},n;
a[i]=i的约数和；
太长了，打不出来
scanf("%d",&n);
for(i=1;i<=n;i++)
{for(j=i;j<=n;j++)
{if(f[i]+a[j]<=n)
{f[i]=max(f[i],f[i-j]+a[j]);}
}
}
printf("%d",f[n]);
}
用背包做

你孬，0/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;
}

看不明白

其实就是背包问题，每个数可以看成一个作品，背包容量为s，每个物品的体积为这个数的大小，价值为这个数的约数和，这样就可以当成01背包来做。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int s,dp[5000]={0};
int tot(int x){
int ans=0;