01背包、完全背包进阶理解（全网最详细）_01背包什么要从后面开始

这是前段时间再刷背包问题时候的一些深入思考，本讲解默认您知晓01背包和完全背包的经典例题，以及基本的解题思路，因为这篇文章属于一些深入思考，对于不同的问题的一些解释

如果您不具备01背包基础知识可以看我的这篇文章

01背包详解

我之前并没有写有关完全背包的经典例题，而是直接写的完全背包的应用实例，如果有需要也可以去翻我的其他文章查看。

---

上篇的01背包文章是我在第一次学习01背包时候的一些看法，现在看来也是十分全面，而本期是我二刷背包问题，相当于是把难点全总结，使语言表述更加精炼，以及对完全背包没有文章的一个补充。话不多说进入正题

对于01背包：

首先二维背包的没什么太多需要讲解的
我只说两点，递推公式和遍历顺序
递推式：dp【i-1】【j】代表的是0-i-1这些东西里，我们取物品，在j这么大的容量背包前提下
能装多少价值东西。
dp【i-1】【j-weight【i】+value【i】这里有两种理解，一个是你可以理解成我们上一个
dp【i-1】【j】代表的是不装i这个物品，而此时需要添加了，我们无法确定当前容量一定
够装进去当前第i个物品，所以需要背包容量减去当前物品重量，腾出这片地方，来装进去i
这个物品，然后加上它的价值。
另一个理解：我们假设此时足够装进去物品i，那么当背包容量不足以装进去该物品时，并且
是正好空出这个物品时所能承载的物品最大价值，加上我刚好能装进去该物品时的价格是多少
为什么这里强调的是刚好空出空出这个物品的容量？
答：因为从刚好空出这个物品容量到刚好能装的进去这一期间，如果题目给定的是排好序的
物品重量顺序，这一期间内，都不能装进去该物品，所以价值是相等的。
那如果不是排好序的重量，假设我们此时可以有其他物品加入进来呢？
那也是一样的，为什么这么说
因为你想加入该物品i，那么一定要有刚好空出的空间，为了避免你说的这种情况就是有空余
容量可能会装进其他物品的情况，所以我们找的临界状态就是刚好装进去
那么问题又回到j-weight【i】这来了，所以这和物品是否重量有序也无关了

还可以这样理解：
01背包要求物品个数只有一个，所以只能依赖于上一层也就是0——i-1物品时候的状态推本层
如果你写成dp【i】【j-weight【i】】+value【i】的话，那在推dp数组时候，可能会把当前物品重复加入背包

遍历顺序：
由于递推公式的原因，画表得知，当前遍历到的价值应该填的数字，是由它的上一行
同列数字，和上一行的左上角某个数字推导而得到，所以遍历顺序先背包还是先物品
甚至是先遍历物品并且逆序遍历背包也行，因为初始化第0行第0列，已经把所有遍历顺序时可能
会遇到的推导方向都填满了。但是不能先遍历背包然后逆序遍历物品，因为这样是竖着遍历的
但是这时候填数从下往上写，递推公式得要想知道当前位置，必须知道它的同列上一行
但此时它的位置还没有被写入！！！二维01背包只有这一种遍历方法是错误的其他都可行

一维数组：

一维数组是滚动数组
就是连续更新该层一维数组，把原本二维数组的数据压缩状态为一维
如何实现？
使用不断更新一维数组各个位置数字实现，并且相邻数字的填写很可能依赖于单向的关系

也只讲遍历顺序和递推公式
递推公式：
dp【j】=max（dp【j】，dp【j-weight【i】】+value【i】
这里的一维数组代表的含义是容量为j情况下，利润最大
dp【j】就相当于二维数组中dp【i-1】【j】这里我是这么理解的
对于当前物品i，我只有两个处理方式，即放物品i到背包中，和不放物品i到背包
那么放不放物品i会影响你本次背包大小吗？？
那肯定不影响啊！所以还是dp【j】
别忘了你二维数组也不过是表示为dp【i-1】【j】仔细看这里的j受影响了吗？
好！然后是dp【j-...这一块
这一块没啥讲的，看二维数组对照一下，还是那么理解就好

难以理解的是遍历顺序
遍历顺序不是像二维数组一样随便
01背包一维数组仅允许先遍历物品再遍历背包，且背包必须为逆序遍历
我前面说了一维数组填数相邻数字会有单项依赖关系
逆序是为了解决背包中连续装物品的问题！
由递推公式第二项可知如果你先遍历小容量背包，那么小容量背包此时就会拥有一个值
再遍历大容量背包时候会用到这个值，乍一看没毛病
实则因为我们此时是先固定遍历一个物品不动去装填背包
那么小容量背包在装小物品很容易装进去，那么大容量背包装入时候
由于第二项它会把该物品连续装入
举例：
    重量    价值
物品0    1    15
物品1    3    20
物品2    4    30
dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30
这能对吗？01背包里保证物品只有一个！

再说为什么不能颠倒物品和背包的遍历顺序
我们已经确定了背包遍历是逆序的，如果你此时先遍历背包
那就是先固定背包容量不变，然后你去内层循环循环物品
自己模拟一下
dp[4]=15
dp[4]=20
dp[4]=30
这能对吗？
4容量时候最大价值不是35吗？
由递推公式可知，当前容量最大价值有一定因素取决于比它小容量的背包
那为什么上面也没有先遍历小容量就对呢？
因为上面背包容量为4和比它小容量的背包在外层改变遍历的物品时候，各背包还能再次
遍历的到，实现了真正意义上的滚动
你先遍历背包相当于锁定容量了，此次遍历完之后遍历不了了
而且你这个思路相当于无论背包容量为多少，只能放入一个物品
那自然是不对的
扩展：
我也想了一下，如果先遍历背包可不可行？
我想改变递推公式或许是可行的
那就是dp【j】和dp【j】+value【i】作比较呗
但是这里你直接这么写无法判断会不会装物品超出容量上限
可以用一个变量累加已经加了多少重量物品
但是这样想的话，那你说我往小背包装东西还有意义了吗？
没有意义啊，直接往大背包装完事了呗，反正大背包也不依赖于小背包状态
就用dp【j】和dp【j】+value【i】这个公式即可以完成对当前背包价值评估
又可以完成对加进来其他物品评估
那超出背包容量了，你又如何加物品向背包内，然后再进行重新装填呢？
这就不行了！
假设最开始装的是重量从大到小排序为w0，w1，w2，w3
那下次装w0，w3，w4还是w1，w2，w3呢？
你如何判断？？
（这里我们假定w0和w1都是很大重量，为了装更多东西，所以设定这两种装
法，实际上装物品方法有很多还）
所以先遍历背包这思路大概没戏

---

完全背包：

把01背包一维弄懂再看！

递推公式和01背包相同
遍历顺序：
可以交换遍历背包和物品的顺序，但是必须要使背包容量从小到大遍历
我们根据01背包一维遍历可知，逆序遍历背包是为了大背包容量不受
小背包容量的影响，如果01背包先遍历小容量背包，由于小容量有值，
物品循环是在外侧，也就是说大容量背包会根据小容量已有的值，重复
加入当前遍历的物品，违背01背包原则。
但是完全背包要求物品无限制使用，所以我们需要小容量的状态来帮助我
们求如果连续放入该物品可能导致价值最大的这么一种情况。
不要忘记递推公式
dp【j】=max（dp【j】，dp【j-weight【i】】+value【i】）

这是完全背包和01背包最本质的不同之处

然后我们再来说说，为什么可以颠倒遍历背包和物品的顺序而不受影响
首先这得益于背包容量的遍历方法，它不用逆序了
这将导致什么问题？
先遍历物品再遍历背包的方法是常规方法，这就不讲了
讲一讲先遍历背包再遍历物品
01背包中不能这样做，理由是先背包容量逆序遍历，先遍历背包会导致
大容量先被遍历，且不能再被修改，且遍历完之后，每个不同容量的背包
只能装进去一个最大价值的物品，不信去模拟
而完全背包由于小容量先遍历，它先装小容量，所以一定是正确的，因为
一开始的小容量不需要依赖于前面的更小容量，而且根据不同的物品遍历
之后，它会装进一个本容量内最大价值，等到遍历大容量背包时候，刚好
能用得上之前遍历完毕的小容量背包的价值，你可以想一下，此时大容量
外侧循环，内侧循环是物品，它分别比较此时价值和要装进不同物品的
价值+所对应的小背包容量最大价值之和，这保证了最后答案的正确性

二维也顺便说一嘴：
二维递推式是
dp【i】【j】=max（dp【i-1】【j】，dp【i】，dp【j-weight【i】】+value【i】）
这里我们假设先遍历物品然后是背包容量
当前位置填数取决于上一层也就是0——i-1物品时，相等容量最大价值
和遍历0——i物品时，如果把当前物品加在背包里价值取最大值
第一项不用解释和01背包相同，第二项有讲究
它是求当前物品遍历中，如果又加了一个当前物品看看会不会得到大价值
因为完全背包可以重复添加物品，
那既然可以重复添加物品那为什么第一项不写成dp【i】【j】？
这里你得明白为什么第一项写成i-1，它单纯是因为物品可不可以重复添加？
实则不然，它代表的是你不加入当前物品时候，最大价值
因为加入当前物品你首先要有足够容量，不是说容量加了1之后就一定够装此时遍历到的物品的
这也是为什么后面的j-weight【i】要这么写的原因
而且这里的第二项，不仅代表可能会装入两个该物品
它代表的是必须装入该物品，且不限制装入个数！
怎么实现？每次的j-weight【i】会为它提供足够空间！

这也就是说什么？
该递推公式导致填数顺序是从左往右，且严格依赖从上到下，从左往右
所以它可以的遍历顺序应该包括
先遍历物品再背包（全正序）、先遍历背包再遍历物品（全正序）
这两种遍历方法

 

---

以上便是这篇文章的全部内容，相信如果认真观看了本篇文章一定会对您的背包问题解题思路有一个新的提升，

都看到这里了如果对您有用的话别忘了一键三连哦，如果是互粉回访我也会做的！

大家有什么想看的题解，或者想看的算法专栏、数据结构专栏，可以去看看往期的文章，有想看的新题目或者专栏也可以评论区写出来，讨论一番，本账号将持续更新。
期待您的关注