acwing5. 多重背包问题 II(二进制优化）

分析

如果直接遍历转化为01背包问题，是每次都拿一个来问，取了好还是不取好。那么根据数据范围，这样的时间复杂度是O(n^3),也就是1e+9，这样是毫无疑问是会TLE的

思路

一个10进制数字可以由二进制数表示，我们把每一种物品都按二进制分堆，并计算每个堆的体积和价值，这样每个堆就是只能使用一次，就变成了01背包，最后遍历所有堆，就可以得到最大价值数。

复杂度

每个物品有s件，那么可以分成log_2 s堆，然后遍历m次，一共有n个物品，所以复杂度为n * m * log_2 s

#include<iostream>
using namespace std;
const int N=12010,M=2010;
int v[N],w[N],f[M];
int n,m;
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){
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    for(int i=1;i<=cnt;i++)
        for(int j=m;j>=v[i];j--)
                f[j]=max(f[j],f[j-v[i]]+w[i]);
    
    cout<<f[m];
    return 0;
}