解决0-1背包问题（方案一）:二维dp数组_0 1背包 二维数组

>>确定dp数组以及下标的含义

dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为j的背包，价值总和最大是多少

（1）不放物品i

例如：当背包的容量是1kg，此时物品1和物品2都是无法放进去的。而物品0是可以放进背包的。

那么此种情况下：

物品0，产生的最大的价值为15

物品1，产生的最大的价值和前面相同，也就是15

物品2，产生的最大的价值和前面相同，也就是15

观察二维表格，以及分析，我们可以这样表示：dp[i-1][j]

思考：dp[i-1][j] 表示什么意思呢？

看表格的 j=0，这一列，正是上文所述的这种情况。也就是背包的容量为 j 的时候，可以放入物品i 或者不能放入物品i 的所能产生的最大的价值!

思考：不能放入物品i时，如何计算其产生的最大价值呢？

只要和前面的值相同即可。相当于 copy 下来。

例如物品1（3kg）放不进容量小于3kg的背包。也就是背包容量为1kg,2kg时，无法放入物品1，那么此时这种情况如何计算最大价值呢？很简单，就是和前面的值相同即可。也就是和物品0产生的最大价值相同。

同理，物品2（4kg）放不进容量小于4kg的背包。也就是背包容量为1kg,2kg,3kg时，无法放入物品2，那么此时和物品1产生的最大价值相同即可。

思考：若能放入物品i呢？

分成两种方案：

【方案一】：放入物品i 能产生的最大价值

【方案二】：不放入物品i能产生的最大价值

选取最大价值即可~

例如：当背包的容量是4kg,可以只放入物品2（4kg），但是产生的价值未必是最大的。此时我们思考一下如果不放入物品2，而是放入其他的物品，计算其重量之和为4kg所能产生的价值。

若不放入物品2，可以有如下思路：

① 只放入物品0（1kg），产生价值15

② 只放入物品1（3kg），产生价值20

③ 先放入物品1（3kg），剩余的1kg的容量，用来放入物品0（1kg），总该产生价值35

那么我们如何实现③这种方案呢？

显然，4kg的容量是可以放入物品1（3kg）并可知其产生的价值为20,那么此时可以计算出剩余容量（1kg）,接着在表格中找出1kg能产生的最大价值为15，然后求其价值总和为35。

观察二维表格，以及分析，我们可以这样表示：

所剩容量能产生的最大价值 + 放物品i的价值 -> dp[i-1][j-weight[i]] + value[i]

（2）放入物品i

例如：当背包的容量是4kg,只放入物品2（4kg），产生价值为30

我们可以发现，应该取 max(不放物品i的最大价值，所剩容量能产生的最大价值 + 放物品i的价值)

上文提及不放物品2，而是放入其他物品时，产生的最大价值为35（也就是放入物品0和物品1所产生的最大价值）。35>30。此时我们便可更新背包的容量是4kg时所能 产生的最大价值为35。

最大价值：dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])

*******************两个方向推出dp[i][j]*******************

>>可以从两个方向推出来dp[i][j]

1.由 dp[i-1][j] 推出，即背包容量为j,里面不放物品i的最大价值，此时 dp[i][j] 就是 dp[i-1][j]

2.dp[i-1][j-weight[i]]推出，dp[i-1][j-weight[i]] 为背包容量为 j-weight[j] 的时候不放物品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]);

【问题(O_O)?思考】：请问是先遍历物品还是先遍历背包呢？

【回答】都可以，因为dp[i][j] 的状态是由正上方和左上方的状态推出来的，无论是先遍历物品还是先遍历背包，都可以知道正上方和左上方的状态，因此dp[i][j]的状态可以被推出。那么选取先遍历物品再遍历背包，还是先遍历背包再遍历物品都是可以的！！！

 在代码体现中，都可以的呢！！！(#^.^#)

// 先遍历物品再遍历背包
for() //遍历物品
    for()//遍历背包
 
 
// 先遍历背包再遍历物品
for() //遍历背包
    for()//遍历物品

****************************************************************************

（3）动规五部曲：

1.确定dp数组以及下标的含义

dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为j的背包，价值总和最大是多少

2.确定递推公式

由 dp[i-1][j] 推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i-1][j]

由 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]);

3.dp数组如何初始化

【注意】关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候会乱掉。

从定义出发，若背包容量j为0的话，即 dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

状态转移方程dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);可以看出 i 是由 i-1 推导出来，那么 i 为0的时候就一定要初始化。

dp[0][j]，即 i 为0，存放编号为0的物品的时候，各个容量的背包所能存放的最大价值很明显，当j<weight[0] 的时候，dp[0][j] 应该是0，因为背包容量比编号0的物品重量小。当 j>=weight[0] 时，dp[0][j] 应该是 value[0]，因为背包容量足够放编号0物品。

dp[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化为多少呢？

其实从动态递推公式：dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);可以看出 dp[i][j] 是由左上方数值推导出来，那么其他下标初始为什么数值都可以，因为都会被覆盖

初始-1，初始-2，初始100，都可以！

但一开始统一把dp数组统一初始化为0，更方便一些。

dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少 

4.确定遍历顺序

有两个遍历的维度：物品与背包重量

思考