01背包问题关于空间优化的讨论

今天学习到了dp（其实以前就学过，不过没学好），再次看到背包问题的时候，突然意识到空间优化过后，他对剩余体积的遍历方式改变了！

看看背包九讲上的伪代码：

这是优化空间之前的

这是优化空间之后的。也是想了一下才想明白。

先来看看优化空间之前的情况

不难发现在优化空间之前，对于每一个放入i个物品的状态，他都是通过i-1状态的数据推出的。i与i-1储存在不同的地方，但是，我们也不难发现所有的f[i,v]都只与f[i-1,v]（v是遍历用的体积，不是最大体积）有关，所以我们决定省去一维，只保存一份i的数据

于是我们将数组改成了这样，依然是用下面的保存i-1的状态。此时i的状态暂时为空

假如我们依然使用二维数组储存时的方式来正向遍历v的话，此时我们来导出第一份f[ci]可以发现他是由f[0]和f[ci]（i-1状态的）得到的，且在得到后就覆盖了i-1状态下的f[ci]暂时还看不出其中的隐患，我们来接着看

略过其中的ci-1个让我们直接来看f[2ci]我们可以返现他是由f[2ci](i-1状态的)，和f[ci](i状态的)得到的，但是我们知道i状态是已经放入过这个i物品了的，再次选用i状态得到的f[ci]意味着再次将一个i物品放入了背包中，这显然和01背包的题意产生了矛盾。由一开始的二维储存方法我们也不难发现i状态的数据应该全部由i-1的数据得到。因此，我们决定进行逆向的循环，见下图的图解

 

我们推了两项之后就可以很方便的发现他覆盖前面的数据，在往前遍历的过程中并不会再次被用到，因此我们选择使用逆向遍历