[学习笔记] 浅谈多重背包二进制优化

做题的时候看到一种写多重背包二进制优化的好方法，特地记录一下

之前写的方法既难理解又难记，而且这个还跑得快（

把 \(num\) 件物品，价值 \(val\) ,花费 \(cost\) 的物品拆分为

\((v,w),(v\times2^1,w\times 2^1),(v\times2^2,w\times 2^2),(v\times2^3,w\times 2^3)...(x,y)\) 最后的是无法被拆的余项

如此便可通过这些 \(\log_{2}num\) 件的物品凑成所有可能的取值状态

与之前写法的不同之处就是先预处理出来了物品数量，也能更加直观地看到“把一些物品合成一个物品”这一思想

#include 
using namespace std;
const int N=1e5+10;
int dp[N],w[N],v[N],n,m,cnt;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;++i){
	int val=read(),wast=read(),num=read();
	for(int j=1;j<=num;j<<=1){
	    v[++cnt]=val*j;
	    w[cnt]=wast*j;
	    num-=j;
	}
	if(num) v[++cnt]=num*val,w[cnt]=num*wast;
    }
    for(int i=1;i<=cnt;++i)
	for(int j=m;j>=w[i];j--)
	    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    printf("%d",dp[m]);
    return 0;
}

\(from:\)