背包DP

题目背景：你有一个容量为 M的背包,有N个物品,每个物品的重量和价值分别为w[i]和c[i],现在选一些物品放入这个背包使装入的价值最大

1. 01背包（每件物品只有1件）：倒序枚举重量，O(N^2)

	E(i,n){
		cin>>w>>c;
		for(int j=m;j>=w;--j) f[j]=max(f[j],f[j-w]+c);
	}

2.完全背包（每件物品无数件）：正序枚举,O(N^2)

		for(int j=w;j<=m;++j) f[j]=max(f[j],f[j-w]+c);

3.多重背包(第i件物品有x[i]件)

(1)当成x[i]次01背包处理,O(NMX)

#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i) 
	F(i,1,n){
		cin>>w>>c>>x;
		F(k,1,x) G(j,m,w) f[j]=max(f[j],f[j-w]+c);	
	}

(2)二进制优化:x[i]=1+2+4+...2^k+tmp,tmp是剩下的一个碎块,O(NMlogX)

	F(i,1,n){
		cin>>w[i]>>c[i]>>x;
		for(int j=1;x-j>=0;j*=2) w[++cnt]=w[i]*j,c[cnt]=c[i]*j,x-=j;
		w[i]*=x; c[i]*=x;
	}//转化过程
//	F(i,1,cnt) printf("%d %d\n",w[i],c[i]);
	F(i,1,cnt) {
//		if(!w[i]) continue;
		G(j,m,w[i]) f[j]=max(f[j],f[j-w[i]]+c[i]);	
	}//dp过程

4.分组背包：每组只能选一个，只要想明白如何满足这个限制即可

	F(i,1,n){
		cin>>x[i];
		F(k,1,x[i]) cin>>w[i][k]>>c[i][k];
	}
	F(i,1,n) G(j,m,0) F(k,1,x[i]) if(j>=w[i][k]) f[j]=max(f[j],f[j-w[i][k]]+c[i][k]);	
	//先倒序枚举容量,再枚举物品,这样能保证f[j]每组只会新放一个物品进去(要么就不放)! 
	cout<<f[m];