背包问题的倒序枚举与正序枚举

这可能是困扰很多人很长时间的问题吧。

先把各个变量列出来

体积为的背包，有个物品，每个物品的体积为，价值为，每个物品装一次，求最大价值

来这看的肯定都是学习过基础背包的人，如果没有可以看我另一篇博客，里面有详细解释——​​点这里​​下面先给出二维的转移方程

首先，对于二维数组的背包来说，正序和逆序是无所谓的，因为你把状态都保存了下来，而一维数组的背包是会覆盖之前的状态的

要想知道，你要从和两个状态转移而来，这两个状态可以直接从二维数组中取出
一维数组的转移方程

表示在执行次循环后(此时已经处理个物品)，前个物体放到容量的背包时的最大价值，即之前的。与二维相比较，它把第一维压去了，但是二者表达的含义是相同的，只不过一直在重复使用，所以，也会出现第次循环覆盖第次循环的结果。

按方程来说，其中有许多对应相等的关系，比如和就是相等的，这是为什么呢？求一下这几个值就好了

1. 前个物品放到容量的背包中带来的收益（）
   由于在执行第次循环时，存储的是前个物体放到容量为的背包时的最大价值，在求前个物体放到容量时的最大价值(即之前的)时，我们正在执行第次循环，的值还是在第次循环时存下的值，在此时取出的就是前个物体放到容量的背包时的最大价值，即。
2. 前件物品放到容量为的背包中带来的收益（）
   由于在执行第次循环前，中保存的是第次循环的结果，即是前个物体分别放到容量时的最大价值，即，则在执行第次循环前，数组中的位置存储就是我们要找的前件物品放到容量为的背包中带来的收益 (即之前的)。

具体来说，由于在执行时，是还没执行到的，因此，保存的还是第次循环的结果。即在执行第次循环且背包容量为时，此时的存储的是，此时存储的是。

相反，如果在执行第次循环时，背包容量按照的顺序遍历一遍，来检测第件物品是否能放。此时在执行第次循环且背包容量为时，此时的存储的是，但是，此时存储的是。

因为，所以第次循环中，执行背包容量为时，容量为的背包已经计算过了，即中存储的是。它会从一开始就装入某个物品，只是为了价值最大，重复是肯定要存在的。即对于01背包，按照增序枚举背包容量是不对的。如下图

我们现在要求时的：

橙色的为数组现在存储的值，这些值是时(上一次循环)存入数组的。相当于

而黄色的是我们要求的值，在求之前，，即

现在要求时的

故；

要注意在求时，它引用的和都是上一次循环的结果

我们现在要求时的

橙色为数组现在存储的值，这些值是时(本次循环)存入数组的。相当于。这是由于，我们是增序遍历数组的，在求时，之前的值都已经在第次循环中求出。

黄色是我们要求的值，在求之前，，即

现在要求时的，故；

其中引用的是而不是

注意一点，在求时，它引用的是本次循环的结果，而是上一次循环的结果

在检测背包容量为时，看物品是否加入

由状态转移方程可知，我们的需要引用自己本身和

由于背包容量为时，可以装入物品，且收益比之前的大，所以放入背包了。

在检测时，肯定要加上物品的收益，而在引用时，时已经加过一次物品，

因此，在枚举背包容量时，物品加入了多次。

然后我们明确三个问题

1. 
2. 状态是由和两个状态决定的
3. 对于物品，我们在枚举背包容量时，只要背包容量能装下物品且收益比原来的大，就会成功放入物品

具体来说，枚举背包容量时，是以递增的顺序的话，由于,则会先计算。在背包容量为时，一旦装入了物品，由于求需要使用，而若求时也可以装入物品的话，那么在背包容量为时，容量为的背包就装入可两次物品。又若是由之前的状态推出，它们也成功装入物品的话，那么容量为的背包就装入了多次物品了。
此时，在计算时，已经把物品能装入的全装入容量为的背包了，此时装入物品的次数一定是最大的
所以，顺序枚举容量是完全背包问题最简捷的解决方案。