一、01背包
(dp[i][j]:=) 决策第(i)种物品、背包总容量为(j)时的最大价值
则(dp[i][j])的取值有两种：
- 不取第(i)种物品，直接继承(dp[i-1][j])
- 在(dp[i-1][k](k≤j-cost[i]))的基础上，取了第(i)种物品，装入。装入之后容量为(j)的背包恰好装满或装不满。
则
答案为(dp[N][T])，(N)为物品种数，(T)为背包容量
空间优化（一维压缩）
如果将(dp[i][j])绘制成如下表格：
.gif)
可以发现第(i)行的结果只与第(i-1)行有关，并且第(i)行第(j)列的格子只与它上方及左上方格子有关。
那么，当更新第(i)行第(j)列的格子之后，第(i-1)行第(j)列往右的格子都是无用的。可以想到，如果第(i)行的数据从右往左更新，那么第(i-1)行与第(i)行可以合并成一行表示，只要从右往左（即倒序）更新，用新的数据覆盖掉原来的数据即可。
这样，(dp)数组就可以压缩成一维：(dp[j])
答案为(dp[T])，(T)为背包容量。
变形——恰好背包
恰好背包与一维背包的不同，仅在于要求容量为(m)的背包恰好装满。
解决方法是，将(dp)数组初始化为(-INF)即可，此外，容量为(0)的背包“恰好装满”时价值就是(0)，因此(dp[0]=0)。
这是因为，在恰好背包中，如果容量为(j)的背包在没有恰好装满的情况下取到了最优解，那么这个最优解其实是无效的，因为它不满足题意。
观察状态转移方程，可以知道：
（1）如果(dp[j-cost[i]])与(dp[j])都是有效状态，则更新后的(dp[j])也是有效状态。
（2）如果只有(dp[j-cost[i]])是有效状态，它一定比原来的(dp[j])更优——(dp[j])是无效状态，值为(-INF)。
（3）如果只有(dp[j])是有效状态，同上。
二、完全背包/无限背包
与01背包的区别在于，完全背包/无限背包问题中的每种物品可以取无限个。
$dp[i][j]:= $ 决策第(i)种物品、背包总容量为(j)时的最大价值
则(dp[i][j])的取值有两种：
- 不取第(i)种物品，则与01背包相同，直接继承(dp[i-1][j])
- 取第(i)种物品。因为可以无限取，所以状态可能由取了1个、取了2个...取了x个等状态转移过来。所以这里不应该从(dp[i-1][j-cost[i]])转移，而应该从(dp[i][k](k≤j-cost[i]))转移。遍历(j)的过程就是让背包容量逐渐增大的过程，状态转移时会不断试图在背包容量允许的情况下多拿一个又一个，并比较能得到的最大价值。所以当(j)遍历结束后，第(i)行的数据都是在不同背包容量下对第(i)种物品的最佳决策。
则
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= cost[i]) dp[i][j] = max(dp[i][j],dp[i - 1][j - cost[i]]);
}
}
答案为(dp[N][T])，(N)为物品种数，(T)为背包容量。
时间复杂度(O(nm))，空间复杂度(O(nm))
空间优化（一维压缩）
观察状态转移方程，容易发现它和01背包有些相似：第(i)行的结果与第(i-1)行有关，但与更上方的行无关。与01背包不同的是，完全背包的第(i)行第(j)列的结果并不只与第(i-1)行有关，还与第(i)行第(j)列左边的值有关。因为大背包的最优解应该由小背包的最优解推出，所以第(i)行第(j)列左边的数据应该比它更先更新。换句话说，对(j)的遍历应该从左往右进行。
由表格可以看出，要用到的数据其实就在同一行。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= cost[i]) dp[j] = max(dp[j], dp[j - cost[i]] + v[i]);
}
}
显然当(j<cost[i])时不会进行任何操作，所以(j)也可以直接从(cost[i])开始枚举
for (int i = 1; i <= n; i++) {
for (int j = cost[i]; j <= m; j++) {
dp[j] = max(dp[j], dp[j - cost[i]] + v[i]);
}
}
时间复杂度(O(nm))，空间复杂度(O(m))
再多一种枚举
上述思路中都是枚举每种物品以及背包容量，可以在此基础上再多一层枚举：枚举第(i)种物品的装入数量。
当第(i)种数量装入0个时，情况等价于不取第(i)种物品。
因为已经直接枚举了第(i)种物品取1个、取2个……的所有情况，所以更新都是基于第(i-1)行的值。
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=j/cost[i];k++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*cost[i]]+k*v[i]);
}
}
}
可以看出状态转移方程与01背包是相同的，因此也可以用与01背包相同的方式进行一维压缩，也就是(j)需要倒序枚举：
当(j<cost[i])时，第(i)种物品只能取0个，因此此时(dp[i][j])直接继承自(dp[i-1][j])，在一维压缩后就相当于对(dp[j])不作任何操作。因此(j)只从(m)枚举到(cost[i])即可。
则
for(int i=1;i<=n;i++){
for(int j=m;j>=cost[i];j--){
for(int k=0;k<=j/cost[i];k++){
dp[j]=max(dp[j],dp[j-k*cost[i]]+k*v[i]);
}
}
}
三、多重背包
这类背包的实质其实和"多重"这个词没什么联系，多重背包与完全背包的区别在于，多重背包中每种物品的数量是给定的有限个。当给定的数量都为1时，就是多重背包的特殊情形——01背包了。
另外，对于第(i)种物品，如果它的总价值（(cost[i] imes amount[i])）(≥)题目所求的背包容量(m)时，对于这个背包而言，第(i)种物品可以视为无限个，可以直接应用完全背包的解法。
时间优化（二进制拆分）
在完全背包的代码中，枚举第(i)种物品的装入数量时，采用的是0、1、2...这样逐个枚举的方式。如果将每一次枚举视为取与不取两种操作的话，即可转化为01背包。但这样每一轮对k的遍历，平均需要(frac{m}{overline{cost[i]}})的时间。能否有别的枚举方式来替代逐个枚举，优化时间？
假设当前第(i)种物品最多能取(c)个，我们可以将十进制数(c)用(2^k)的和式来表达，如(10=2^0+2^1+2^2+3)，除最后一个数外，前面的数构成以(1)为首项，公比为(2)的等比数列。
这样，就可以将(10)分成(4)堆，且可以证明，这(4)堆的不同组合方式可以构成(1 sim 10)之间的所有正整数。
这样我们就把(1 sim 10)逐个枚举的过程，变成了枚举这(4)堆“取与不取”的过程。也就是说通过二进制拆分，我们将完全背包转化成了01背包。
for(int i=1;i<=n;i++){
for(int k=1;k<=amount[i];k<<1){
//先拆分，再01背包，所以先对k遍历再套j的遍历
for(int j=m;j>=k*cost[i];j--){
dp[j]=max(dp[j],dp[j-k*cost[i]]+k*v[i]);
}
amount -= k;
//将分完的堆从当前物品总数中减出来
}
//对最后剩下的那一堆也要一次01背包
//注意此处的amount已经进行过多次减法，不是最开始的amount了
for(int j=m;j>=amount*cost[i];j--){
dp[j]=max(dp[j],dp[j-amount*cost[i]]+amount*v[i]);
}
}
四、混合背包（01背包+完全背包+多重背包）
给出(n)种物品，有些可以取无限个，有些只能取有限个，这样的情形就要结合以上三种背包算法。
我们注意到，这三种背包的代码有一些共同点：第一重循环都是对(i)的遍历、都可以将(dp)数组压缩成一维、在对(j)的遍历中仅用到(cost[i])与题目所求的背包容量(m)这两个参数。
那么，可以尝试将三种背包算法各自封装成函数：
//01背包
void ZeroOnePack(int cost,int value){
for (int j = m; j >= cost; j--) {
dp[j] = max(dp[j], dp[j - cost] + value);
}
}
//完全背包
void CompletePack(int cost, int value) {
for (int j = cost; j <= m; j++) {
dp[j] = max(dp[j], dp[j - cost] + value);
}
}
//多重背包
void MultiplePack(int cost, int value,int amount) {
if (cost * amount >= m) {
CompletePack(cost, value);
return;
}
//如果这个物品amount个的总价值已经大于等于背包容量，则对于这个背包来说，这个物品可以视为有无限个
for (int k = 1; k <= amount; k <<= 1) {
ZeroOnePack(k * cost, k * value);
amount -= k;
}
ZeroOnePack(amount * cost, amount * value);
}
那么我们的主函数可以简洁地写成这样：
int main(){
输入数据
for(int i=1;i<=n;i++){
if(第i种物品数量为1)
ZeroOnePack(cost[i],v[i]);
else if(第i种物品数量无限)
CompletePack(cost[i],v[i]);
else if(第i种物品数量有限)
MultiplePack(cost[i],v[i],amount[i]);
}
cout<<dp[m];
return 0;
}
五、多维背包
多维背包的特点是，一个物品有多种费用，当选择该物品时，必须同时付出这多种费用。同时也会给出背包对这多种费用的容量。
最简单的是二维背包：对于第(i)种物品，其费用为(cost1[i])与(cost2[i])，价值为(value[i])，求容量为(m_1)（针对第一种费用）、(m_2)（针对第二种费用）的背包可得到的最大价值。
在一维背包中，只需要枚举一次背包容量for(int j=1;j<=m;j++)，类比一下，二维背包只需要再加一层循环即可。当然(dp)数组也需要再加一维：(dp[i][j][k])。
那么(dp[i][j][k])的取值有两种：
- 不取第(i)种物品，直接继承(dp[i-1][j][k])
- 取第(i)种物品（如果能），那么在(dp[i-1][j-cost1[i]][k-cost2[i]])的基础上装入第(i)种物品
状态转移方程：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m1; j++) {
for (int k = 1; k <= m2; k++) {
if (j >= cost1[i] && k >= cost2[i])
dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - cost1[i]][k - cost2[i]] + v[i]);
else dp[i][j][k] = dp[i - 1][j][k];
}
}
}
答案是(dp[n][m1][m2])
空间优化
与前面几种背包类似，(dp)数组中的第1维([i])是可以省去的。且由状态转移方程可知，第(i)层的值只与第(i-1)层有关，这意味着我们可以类比一维背包的优化方式，通过对两种容量的倒序枚举进行优化。
for(int i=1;i<=n;i++){
for (int j = m1; j >= cost1[i]; j--) {
for (int k = m2; k >= cost2[i]; k--) {
dp[j][k] = max(dp[j][k], dp[j - cost1[i]][k - cost2[i]] + v[i]);
}
}
}
答案是(dp[m1][m2])
六、分组背包
给出(n)种物品，每种都有它所属的组。若对每一组最多只能选择一个物品，问给定背包容量下能得到的最大价值。
(dp[i][j]:=) 决策第(i)组中的物品、背包总容量为j时的最大价值
则(dp[i][j])的取值有两种：
- 不取第(i)组中的物品，直接继承(dp[i-1][j])
- 在(dp[i-1][k](k≤j-cost[p]))的基础上，取了第(i)组里的第(p)个物品，装入。
则$$dp[i][j]= egin{cases} dp[i-1][j-cost[p]]+v[p]& ext{j≥cost[p]} dp[i-1][j]& ext{其他} end{cases}$$
代码自然是三重循环：第一重枚举每一组，第二重枚举背包容量，第三重枚举当前组中的每种物品。
注意第二三重循环的顺序，必须先枚举背包容量而后才枚举组内物品。如果顺序调换，则可能导致装入了同一组的多个物品。
七、有依赖的背包
给出(n)种物品，且物品之间存在依赖关系：要选择物品(y)，必须先选择物品(x)。
称不依赖于其他物品的物品为主件，依赖于其他物品的为附件。
如果将不同主件及其附件集合视为不同的物品组，这就有点像分组背包问题。但区别在于，这里可以选择多个附件，导致问题规模的指数级增加。
将问题一般化，那么物品之间的依赖关系会构成一棵树。注意，主件与主件之间其实是相互独立的，但我们可以在此之上再增加一个费用为0的根节点，便于递归。
解决思路如下：对于一个父节点(i)，先求子结点在背包容量为(m)时的最优结果（对于叶子节点来说，就是来一遍01背包），再在此基础上尝试装入父节点。如果完全装不了，则方案是不可能的，此时要将之前得到的结果清空。
(dp[i][j]:=) 以节点(i)为父节点、背包容量为(j)时的最大价值。