2019-01-19

多重背包：每种东西有多个，因此可以把它拆分成多个01背包

优化：二进制拆分（拆成1+2+4+8+16+...,分别表示2的n次幂）

比如18=1+2+4+8+3，可以证明18以内的任何数都可以用这几个数的和或差表示（每个数只能用一次）（0时则背包为空），

所以就把2个，4个....绑定为一个物品，和一个一个的效果是一样的

这样就减少了拆分出来的物品的数量。（从n到log n)

代码

#include<cstdio>
using namespace std;
const int maxn = 200005;
int n,m,a,b,c,cnt,ans,f[maxn],v[maxn],w[maxn];
int main() {
    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 *= 2){
            c -= j;
            v[++cnt] = a*j;//区分++cnt和cnt++ 
            w[cnt] = b*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]);
            ans = max(f[j],ans);
        }
    printf("%d",ans);
    return 0;
}