dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
递推公式：
dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
那么可以有两个方向推出来dp[i][j]：
- 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
- 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其中递推公式中dp[i - 1][j - weight[i]] + value[i]是比较疑惑的。
使用如下示例说明对递推公式的理解：
背包最大重量为6，问背包能背的物品最大价值是多少？
| 物品 | 重量 | 价值 |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
以计算dp[2][6]为例，即计算从下标为[0-2]的物品里任意取，放进容量为6的背包，价值总和最大是多少。
- 不放物品2：
想计算dp[2][6]，计算下标为[0-2]的物品里任意取，放进容量为6的背包，价值总和最大是多少。定义一定要理解清楚。
现在我们有个前提，不放物品2。那么从下标为[0-2]的物品里任意取，放进容量为6的背包 和 从下标为[0-1]的物品里任意取，放进容量为6的背包 是等价的。所以dp[2][6] = dp[1][6]，很好理解。 - 放物品2：
想计算dp[2][6]，计算下标为[0-2]的物品里任意取，放进容量为6的背包，价值总和最大是多少。定义一定要理解清楚。
现在我们有个前提，放物品2。这个前提的意思就是：在当前容量为6的背包里，我一定要把物品2放进去。我们假设放进去一定能放进去吗？不一定，但是如果放不进去，那么就等价于第一种场景，相当于不放物品2。
下面我们假设在容量为6的背包里，我们一定会把重量为4的物品2放进去。那么相当于容量为6的背包里一定要放重量为4的物品2，那么容量为6的背包里还能用的空间为：6-4=2，既然我们一定要放物品2，那么，dp[2][6]：从下标为[0-2]的物品里任意取，放进容量为6的背包，价值总和最大。就变成了，物品2的价值（已经假设一定要放进去） + 从下标为[0-1]的物品里任意取，放进容量为2的背包（因为放了物品2之后，容量为6的背包里容量只剩下2了），价值总和最大。
所以dp[2][6] = 物品2的价值 + d[1][当前的容量 - 物品2的重量] = dp[2][6] =4 + d[1][6 - 4] = dp[2][6] =4 + d[1][2]。
重点是要理解，第二种场景下（放物品2），我们假设了在当前容量为6的背包里，我一定要把物品2放进去。
转自：https://www.jianshu.com/p/9dc771f90523
标签：背包,下标,容量,递归,公式,放进,物品,动态,dp From： https://www.cnblogs.com/unlasting/p/16818704.html