题目背景：你有一个容量为 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];