题解 P1776 【宝物筛选_NOI导刊2010提高（02）】

· · 题解

很明显的一道多重背包问题

状态转移方程也很常规

唯一的问题就是数量实在是太多了

直接写模板的话肯定会超时

那么就需要用到优化了

这里用到的是二进制优化

首先我们要知道二进制优化的原理

以19为例，如果我们拆分成1,2,4,8,3

我们就可以用之前的五个数表示出1~19的所有数

那么五个数是怎么来的呢

其实就是相加小于等于该数的2的幂次方（1,2,4,8）和那个数与和的差值（3）

如果我们对于每个物品进行二进制优化就可以增加空间复杂度而减低时间复杂度了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans,cnt=1;
int f[1000005];
int w[1000005],v[1000005];//记得将数组开大
int main()
{
    int a,b,c;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        for(int j=1;j<=c;j<<=1)
        {
            v[++cnt]=j*a,w[cnt]=j*b;
            c-=j;
        }
        if(c) v[++cnt]=a*c,w[cnt]=b*c;
        //二进制优化,拆分 
    }

    for(int i=1;i<=cnt;++i)
     for(int j=m;j>=w[i];--j)
      f[j]=max(f[j],f[j-w[i]]+v[i]);
    //简单的多重背包 
    printf("%d\n",f[m]);
    return 0;
}