概述

• 为什么用dp来做背包问题？
  因为dp快。为什么快？因为dp避免了枚举每一个单独的状态，而是用一个值代表多个状态的集合，这样的话，转移就只会在状态集合间发生而不是单个的状态间，并且在转移的过程中会不断地过滤掉非最优状态。
• 背包问题有什么用？
  很多的dp问题都可以转化为背包问题：
  • 整数划分
  • 最接近目标价格的甜点成本

01背包

二维

• f[i][j] = max(f[i-1][j], f[i-1][j-v]+w)

一维优化

• （注意要逆向枚举，因为当前的状态由上一行的状态转移而来）
• f[j] = max(f[j], f[j-v]+w) (for(j = m; j >= v; j --))

完全背包

二维

• f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, ...) (1)
• f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v]+w, f[i-1][j-3v]+2w, ...) (2)
  (2) 代入 (1)中第一项之后的所有项 得
• f[i][j] = max(f[i-1][j], f[i][j-v]+w)

一维优化

• （注意是正向枚举，因为当前的状态由当前行的状态转移而来）
• f[j] = max(f[j], f[j-v]+w) (for(j = v; j <= m; j ++))

多重背包

• f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, ..., f[i-sv]+sw) (3)

$O(NMS)$的做法

• 把同种物品的多个物品拆成多种同样的物品，这样每种物品就只有一个了，转换成了01背包。
• 实现的时候，先枚举物品，再枚举背包体积，最后枚举决策。

$O(NMlogS)$的做法（二进制优化）

• 也是把同种物品的多个物品拆掉，但是这次不是拆成一个一个的，而是拆成二进制个数（1,2,4,8,…)
• 这样既能优化复杂度，又保证能枚举出所有的决策。
• 注意多重背包与完全背包的区别，多重背包不能用完全背包的优化思路，因为物品个数有限制，如果多重背包仿照完全背包写出式(2)：
  f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v]+w, ..., f[i-1][j-sv]+(s-1)w, f[i-1][j-(s+1)v]+sw) (4)
  会发现(3)的后段和(4)对不齐，因为(4)多出一项f[i-1][j-(s+1)v]+sw.

分组背包

• 分组背包实际上是多重背包的一般情况。我们把多重背包的一种物品的每种决策（选择1个物品，2个物品，3个物品…）打包成一种物品，这样多重背包原来的“一种物品”就变成了分组背包的“一组物品”。
• 所以说，分组背包这种一般情况没有多重背包那样的优化，只能通过“先枚举物品，再枚举体积，最后枚举决策”的$O(NMS)$做法来做。