目录

问题介绍

模板题演示

问题分析(如何使用动态规划)

状态表示：

一维dp

二维dp

状态转移方程

初始化

填表顺序

返回值

---

之前出过0/1背包的问题但是很多人私信我反应没有听明白怎么做的，今天我找到了模板题再进行更详细的解读。我们先从问题介绍开始

问题介绍

0/1背包问题是经典的动态规划问题之一，在计算机科学中广泛研究和应用。它的名称来自一个理想化的场景：给定一组物品，每个物品有一定的重量和价值，目标是在一个固定容量的背包内尽可能装入具有最大价值的物品。这里的“0/1”表示每个物品要么被选择（1），要么不被选择（0），即不能只选择部分物品。

所以问题的背景就是一个装东西并考虑部分装与不装最后计算最大价值的问题。

模板题演示

DP41 【模板】01背包

问题分析(如何使用动态规划)

相信大家已经读过题了吧。我们先分析问题(1)，对于问题1来说既然要求的是不超过背包的容量就算一种合理的放置方法，所以如果定义背包的总容量为j的话，那不超过背包容量的放置结果所用的空间就是[1, j]。

因为如果要放入第i个物品时(选择i物品时)，由于0/1背包的特点是物品只有放入和不放入两种状态，不可以多次放入，所以就完全取决于第i - 1个物品被放入或者不放入时的背包所剩空间的。

只考虑前一个商品吗？那不是还要知道其是放入还是不放入，有点麻烦，因为放入商品其实是在一个给定的范围的，所以我们可以认为当1 - i这个物品区间要放入i这个物品时就要取决于1 - (i - 1)这个物品区间里面放入的物品的体积总和。所以此时后一个状态取决于前一个状态了，这样我们可以使用动态规划来解决这个问题。

推理出了要使用动态规划算法进行解答，我们就必须依照着动态规划5步法进行分析。

状态表示：

状态表示就是表示dp表内部元素的含义。既然要求的是放入若干个商品的最大价值，所以呀dp表里面存的就是最大价值，这个纯粹属于题目要求，然后我们分析dp表内表示的东西也就是最大价值会受到哪些限制条件，经过分析可以知道，1。背包空间的大小，2。选择物品的范围。那我们是使用一个限制条件来表示最大价值(一维dp)，还是两个限制条件共同表示最大价值(二维dp)，那我们先试一下一维的dp能不能推出状态表达式吧(经验)，一上来就开始考虑二维的dp表达式是非常不负责任的做法：

一维dp

1。如果只用第一个限制条件的话：

此时dp[j]：从1到j个空间选择商品的最大价值。

这个状态表示一听起来就很有问题，就是选商品的范围没有给出来，也不知道dp[j - 1]选了多少个商品了，所以这个状态表示是一定推不出状态表达式的！！！

2。如果只用第二个限制条件的话：

此时dp[i] ：从1到i个物品选择若干个的最大价值。

这个状态表示一听起来也很有问题，就是不知道此时选完商品后的背包容量是多少，如果满出来了怎么办，也不知道dp[i - 1]之后背包的所剩空间有多少，万一此时背包的所剩空间不能装下第i个商品了呢？那第i个商品还选吗？，所以这个状态表示也是一定推不出状态表达式的！！！

总结：我们发现状态表是解决动态规划的题的很重要的一步，如果不能表达出一个好的状态表示动态规划的题就无从下手了。

所以我们经过一维dp的分析可知着两个限制条件是来共同限制最大价值的，缺一不可的，所以既然两个限制条件i和j都要使用那，结合一维的状态表示可以得出：状态表示dp[i][j] = dp[i] + dp[j]

二维dp

这样将两个限制条件结合可得，dp[i][j] 表示从第1到i个物品中选择若干个物品使这些物品装入背包后的体积不大于j的最大价值。

这个状态表示就非常的合理且可以推导出状态表达式了！！！

这个上面以一块区间作为dp状态表示的范围可以说是经验所得了，从一维推到二维也是经验所得，反正一维的表示不了就转二维的了。所以状态表示就是经验+题目要求

状态转移方程

有了一个合理的状态表示，我们就可以开始写动态规划第二重要的状态转移方程。

状态表示从第1个物品到第i个物品到第i个物品的最大总价值需要先考虑1->i - 1的装包情况的，那么从1-i和从1-i - 1的区别就是是否多放入i物品使得最大总价值发生变化，所以我们写状态转移方程的时候dp[i][j]只需要考虑在1-i的范围内第i个物品是否放入就可以了。根据经验：需要考虑第i个元素是否放入，也就是结尾元素是否放入。

若dp[i][j]中第i个物品不能放入，那这时dp[i][j]的值就完全取决于在1到i - 1个物品的范围里面随机选入物品的总体积不大于j的最大价值也就是等于dp[i - 1][j]，这里肯定会有一种最大价值的选法使得背包的体积不大于j，注意这里是不大于j，不选也是一种选法只不过价值为0，因为不选第i个物品所以dp[i][j]的最大价值就是dp[i - 1][j]的最大价值。

若dp[i][j]中第i个物品可以放入，那就说明在放入i物品之前需要有充足的空间，也就是说j - v[i] >= 0的才可以放入第i个物品，为什么可以取=，因为这样就相当于只取了i物品，前面1到i - 1都没有取，这样也是合理的，上面的j为放入i物品后的背包总体积不大于j体积，所以状态转移方程有：

dp[i][j] = dp[i - 1][j - v[i]] + w[i] 其中j - v[i] >= 0，为什么还需要加上w[i]呢，因为dp[i][j]表达的是总价值，既然需要放入i物品那i物品的价值也是需要最后加入的。

若以上两种情况放和不放都可以满足的话，那就说明dp[i][j]有两种放法，由于根据状态表示要的是最大价值，所以还需要对这两种方法所求得的最大价值再进行取最大值的操作。所以：

dp[i][j] = max(dp[i - 1][j]，dp[i - 1][j - v[i]] + w[i])  其中j - v[i] >= 0

如果无法放入物品i，则dp[i][j] = dp[i - 1][j]，因为上面已经推过了不放入物品i的这种情况是永远存在的。

由于细节比较多，自己在整理和学习的时候要时刻的清晰认识到i，j和状态表示是什么意思。

初始化

由于dp[i][j]中i为了让商品编号和数组下标对应(1号商品对应1下标)，观察状态转移方程i从1开始也是为了防止i - 1越界访问的问题，所以i是从1到i的，认为j = 0不合理，所以j的·取值范围是1到j所以dp数组就相当于在前面多开了一行和一列(i = 0，j = 0)，那只需要初始化i = 0和j = 0那一行就可以了，因为dp表里面别的数据都可以通过这一行和一列推出来，这样多开一行和多开一列的初始化方法在动态规划里面还是比较常见的。所以当i = 0时，由于没有物品但又要使总体积不大于j所以没有物品只能相当于不选任何物品然后总体积为0才有可能 <=j 所以这一行的dp值都是0，注意这里是选与不选的问题，当j = 0时，由于物品可以有i个但是要使得背包总体积为0，所以只能不选任何物品才能满足，所以这一列的dp值也为0，除此之外的其他值可以初始化成任何值，为了方便都初始化成0。

初始化的问题主要是细节比较多，需要来回画图揣摩。

填表顺序

由于填表顺序完全由状态转移方程决定的，所以我们再来看一下这个方程。

友情提醒上面这个表达式的绿色的字不需要看，因为是第2问的限制条件，其实第2问背包只能为j体积和第一问的区别就是这些绿色的字迹。

由于填第i行时需要第i - 1行的值，填第j列时有可能会需要j - v[i]的值，所以我们需要从左上到右下的顺序填表。

返回值

由于本题要求的是从前i个物品中挑n个物品，使背包体积不大于j的最大价值，此时j的最大值为V，i的最大值为n，所以需要返回的最终结果就是dp[n][V]

至此我们这个题的第一个小问就解决了，由于这个题有两个问题对应着0/1背包问题的两种基本情景，所有代码会在之后的第2问讲完之后一起放出，记住千万不要因为这个是模板题而去背模板，背代码，要去理解上面我带着分析的解决问题的过程，因为着方面的题目不会这么直白的告诉你是用的0/1背包来解决的！！！

还有我们每次在做动态规划问题的时候都要遵循这5步进行解题。都想好了再开始写代码正确率和效率会高很多！！！