P1734 最大约数和
最大约数和
题目描述
选取和不超过 S 的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入格式
输入一个正整数 S。
输出格式
输出最大的约数之和。
样例 #1
样例输入 #1
11
样例输出 #1
9
提示
【样例说明】
取数字 4 和 6，可以得到最大值 (1+2)+(1+2+3)=9。
【数据规模】
对于 100 % 的数据，1 ≤ S ≤ 1000。
分析
典型的01背包
Q：01背包是什么？
A：背包问题中最简单的问题。有n件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
Q：01背包有什么特别之处？
A：给定几种物品，每种物品有且只有一个，并且有价值和体积两个属性。
Q：在求解01背包的过程中每个物品要考虑几种情况？
A：对于每个物品只需要考虑放与不放两种情况。
1.不放，则不需要处理。
2.放，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。
由此可以得出，状态转移方程是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
解释一下这个方程，f[i-1][v]指的是不放这件物品，而f[i-1][v-c[i]]+w[i]指的是将第i件放入背包之后的总价值。
for (int i=2;i<=n;i++) {//1的约数和为0，直接从2开始
for (int j=i;j<=n;j++) {
f[j]=max(f[j],f[j-i]+a[i]);
}
}
for(int i=1;i<=n;i++)
for(int j=n;j>=i;j--)//01背包基本模板
dp[j]=max(dp[j],dp[j-i]+a[i]);//i本身当做价钱，a[i]当做价值；
回到题目本身，约数和用一个简单的函数就可以求出来了。
int yueshuhe(int m){
int ans=0;
for (int i=1;i<m;i++){
if (m%i==0) ans+=i;
}
return ans;
}
int find(int x)
{
int ans=0;//ans记录x的约数和（注意，不包括自己），还有，一定要将ans初始化为0，本蒟蒻因为没有初始化浪费了半个小时；
for(int i=1;i<x;i++)//不包括x本身
if(x%i==0)
ans+=i;
return ans;
}//简单函数
注意，这里的ans一定要在函数里面初始化为0，如果定义成全局变量会叠加。嗯，会挂。不信你试试吧，我不拦你。
Q：状态转移方程是啥？能吃吗？（问着问着就饿了）
A：能吃。
END
提交答案
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[1001],dp[1001],b[1001];
int find(int x)
{
int ans=0;//ans记录x的约数和（注意，不包括自己），还有，一定要将ans初始化为0，本蒟蒻因为没有初始化浪费了半个小时；
for(int i=1;i<x;i++)//不包括x本身
if(x%i==0)
ans+=i;
return ans;
}//简单函数
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
a[i]=find(i);//进行一步预处理，a[i]表示i的约数和（不包括自己，第3遍强调）
for(int i=1;i<=n;i++)
for(int j=n;j>=i;j--)//01背包基本模板
dp[j]=max(dp[j],dp[j-i]+a[i]);//i本身当做价钱，a[i]当做价值；
printf("%d ",dp[n]);//输出就好了
}