题目描述

二进制优化的多重背包

算法1

(暴力枚举) $O(nmlogs)$

二进制优化，就是依据k位二进制可以表示2^(k+1)-1的数，进而把可选多个的物品改为只可以选一个的物品（多个物品叠加）。

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

const int N=25000,M=2010;

int f[N];
int n,m;
int v[N],w[N];

//所谓二进制优化，只不过是把多重背包转换成01背包



int main()
{
    cin>>n>>m;

    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,s;

        cin>>a>>b>>s;

        int k=1;
        while(k<=s)
        {
            cnt++;
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(s>0)
        {
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }

    }

    n=cnt;

    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

    cout<<f[m]<<endl;

    return 0;



}