最近在洛谷上写了几个背包的板子题，总结一下。
1. 01背包
01背包问题一般是：告诉你有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
对于每一件物品我们可以选择取还是不取。
我们可以定义一个二维数组 f[i][j] 来表示对前i个物品，你选择取或不取后，这个容量为V的背包中最大的价值为多少。
对于第i个物品，当我们选择取的时候：f[i][j] = f[i-1][j-w[i]]+c[i] ；（显然此时 j 的范围为 w[i]~V ）
当我们选择不取的时候：f[i][j] = f[i-1][j]；
for(int i = 1; i <= N; i++) { for(int j = 0; j <= V; j++){ if (V < w[i]){ f[i][j] = f[i-1][j]; }else { f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+c[i]); } } }
显然，我们能把数组可以将f缩减成一维数组，从而达到优化空间的目的，状态转移方程转换为:
f[j] = max(f[j],f[j-w[i]]+c[i])
for(int i = 1; i <= N; i++) { for(int j = V; j >= w[i]; j--){ f[j] = max(f[j],f[j-w[i]]+c[i]); } }
例题：P2871 [USACO07DEC]手链Charm Bracelet
2. 完全背包
完全背包问题一般是：告诉你有N种物品和一个容量为V的背包，每种物品不限数量。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
和01背包类似，我们对于每种物品可以不取、取一件、甚至取多件，只要容量够。
for(int i = 1; i <= N; i++) for(int j=w[i]; j<=V; j++) f[j]=max(f[j-w[i]]+c[i], f[j]);
3. 多重背包
多重背包问题一般是：告诉你有N种物品和一个容量为V的背包，每种物品数量为num[i]。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
我们可以把它转化为01背包问题。
朴素算法：
for (int i = 1; i <= N; i++) for (int j = V; j >= 0; j--) for (int k = 0; k <= num[i]; k++) { if (j-k*w[i]<0) break; f[j] = max(f[j],f[j-k*w[i]]+k*c[i]); }
进行二进制优化：
先将num[i]个物品分成多个物品，它们的重量方便为 c ={ k*c[i] | k = 1 2 4 8 ...，如果数量有剩余则剩下的算一个物体}
然后按01背包做。
int cnt = 0; for (int i = 0; i < N; i++){ scanf("%d%d%d",&wi,&ci,&numi); for (int j = 1; j <= numi; j<<=1){ w[cnt] = j*wi; c[cnt] = j*ci; numi-=j; cnt++; } if (numi){ w[cnt] = numi*wi; c[cnt] = numi*ci; cnt++; } } for (int i = 0; i < cnt; i++){ for (int j = V; j >= w[i]; j--){ f[j] = max(f[j],f[j-w[i]]+c[i]); } }