LintCode_125.md

LintCode_125 backpack II

背包型动态规划

B站课程九章算法——DP5_9C(1)

背包问题的状态一定要把总承重放进去每个装物品的方案总重量都是0-M

如果对于每个总重量，我们能知道对应的最大价值是多少，就能知道答案

确定状态
需要知道N个物品
- 能否拼出重量W（W=0,1,...M）
- 对每个重量W的最大总价值是多少？
- ==最后一步==：最后一个物品（重量An-1,价值Vn-1）是否进入背包？
```
	 选择一：最后一个物品不进入。如果前N-1个物品能拼出W，最大总价值是V，那么前N个物品就也能拼出W并且最大总价值是V
```
```
    选择二：最后一个物品进入背包。如果前N-1个物品能拼出W-An-1,最大总价是V，则再加上最后一个物品(重量An-1，价值Vn-1),能拼出W，最大总价是V+Vn-1
```
- ==子问题==：要求前N个物品能不能拼出重量0,1,...M，以及拼出重量W能获得的最大价值。需要知道前N-1个物品能不能拼出重量0,1....M，以及评出重量W能获得的最大价值
- ==状态==： $$ f[i][w]=用前i个物品拼出重量w时最大总价值（-1表示不能拼出w） $$
转移方程

$$ f[i][w] = max{f[i-1][w],f[i-1][w-A_{i-1}]+V_{i-1}|w>A_{i-1} 且f[i-1][w-A_{i-1}]\neq-1} $$
初始条件和边界情况
- 初始条件
  - f[0][0]= 0:0个物品可以拼出重量0，最大总价值是0
  - f[0][1..M] = -1:0个物品不能拼出大于0的重量
- 边界情况
  - f[i-1][w-$A_{i-1}$] 只能在w$\geq A_{i-1}$,并且$f[i-1][w-A_{i-1}]\neq-1$时使用
计算顺序
- 初始化 f[0][0],f[0][1],....f[0][M]
- 计算前1个物品拼出各种重量的最大价值：f[1][0],f[1][1],...f[1][M]
- 答案：$\max \limits_{0\leq j \leq M} {f[N][j] \mid f[N][j] \neq -1 }$