01背包问题和经典例题——最大约数和

· · 个人记录

经典的01背包问题是这样的：

有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫做01背包，0表示不取，1表示取]

这种题很明显

用贪心是做不出来的

往往贪心是得不到最优解的，

原因只有一个：目光短浅

那到底怎么办呢，大家看我给一道难水题

最大约数和

题目描述

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

输入格式

        输入一个正整数S。

输出格式

输出最大的约数之和。

输入输出样例

输入

11

输出

9

说明/提示

样例说明

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

数据规模

s<1000

思路

这题只要算出来每个数的约数和我们就能发现就是个很明显的01背包问题

咱们假设这题最优解为：dp[i]

小声bb：本来背包问题就是动态规划

对于每个物品只需要考虑放与不放两种情况。

1.不放，则不需要处理。

2.放，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

由此可以得出，状态转移方程是：

dp[i]=max(dp[i-j]+a[j],dp[i]);

Code


#include <bits/stdc++.h>
using namespace std;
int s,a[1005],u[1005];
int find(int x)//求每个数最大公约数的和
{
    int ans=0;//一定要把ans初始化为0
    for(int i=1;i<x;i++)
    if(x%i==0)
        ans+=i;
    return ans;
}
int main()
{
    cin>>s;
    for(int i=1;i<=s;i++)
    a[i]=find(i);//把和赋值给a[i]
    for(int i=1;i<=s;i++)
    {
        for(int j=s;j>=i;j--)  
        {
            u[j]=max(u[j-i]+a[i],u[j]);//01背包基本模板:和我刚刚讲的一模一样
        }  
    }  
    cout<<u[s];
    return 0;//完美收场
}

NICE~