二进制多重背包，hdu2191，谈谈自己的理解和看法

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2191

假如同一个物品出现多次，那么可以将其看成不同的物品，然后用01背包来做。

有一个更快的方法就是利用二进制。对于任何一个数字都可以用二进制表示，那么将这个物品的数量拆成二进制（1，2，4，8）的方式再使用01背包就会快很多。

例如：物品i，质量为wei[i],价值为val[i],有3个，那么可以看成2个物品： 质量分别为 1*wei[i]   2*wei[i]  以及价值分别为 1*val[i] ，2*val[i]的物品

取1个，2个，3个物品都可以用上面表示出来。

请允许我使用语言来描述代码的运行。

声明一个变量i 表示有i个物品，然后让i=1，跑一次01背包，然后i*=2，再跑一次01背包。

是吗？那么问题来了，假如我有2个物品，该怎么表达呢？

在i=1跑01背包，i=2跑01背包，欸？虽然可以跑出1和2，但是怎么也把3给跑出来了？

在利用二进制计算的时候

无论你是否需要，二进制都会表示出其所能表示的所有数字。

所以我们需要提前停掉

只需要运行到i=2的情况就行了，那么剩下的差值就作为另外一个01背包就可以了

（用二进制表示）

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[4000];  // 金钱能买到的最重的大米 
int pla[4000],wei[4000],num[4000];
void compete_beg(int num){
	for(int i=pla[num];i<=n;i++){
		dp[i]=max(dp[i],dp[i-pla[num]]+wei[num]);
	}
}
void zo_beg(int a,int b){
	for(int i=n;i>=b;i--){
		dp[i]=max(dp[i],dp[i-b]+a);
	}
}
int main() {
	int C; cin>>C;
	while(C--){
		cin>>n>>m;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=m;i++){
			scanf("%d %d %d",&pla[i],&wei[i],&num[i]);
		}
		for(int i=1;i<=m;i++){
			if(pla[i]*num[i]>n) compete_beg(i);
			else{ // (j<<1)-1 代表 最大能表达的数字 
				int j;
				for(j=1;(j<<1)-1<=num[i];j<<=1) zo_beg(wei[i]*j,pla[i]*j);
				zo_beg(wei[i]*(num[i]-j+1),pla[i]*(num[i]-j+1));  // 中间商的差价！！ 
			}
		}
		cout<<dp[n]<<endl;
	}
	return 0; 
}