理解0-1背包问题使用一维数组的做法

最近在学习0-1背包问题的时候，发现了一种使用滚动数组的方法来使需要的空间从二维压缩成一维，但是这种压缩有一个条件，就是对于背包容量V的枚举必须是从右往左（即从最大容量开始枚举），而使用二维数组则没有这个限制。一开始也是没有想通原因，但是走了一遍流程之后就理解了这个问题。

以下面一个例子为例，w[i]表示物品的重量，c[i]表示物品的价值，背包容量V=8：

当采用二维数组时，应该得到如下的矩阵：

而采用一维数组时（这里把V扩充到10）

当I = 1时得dp数组

当I = 2时，如果从左向右枚举：

这个时候显然出现了问题，可以看到dp[10] = max(dp[10], dp[10-5]+5) = max(4, 5+5) = 10，而我们期望的值应该是9！

在自己手动模拟的时候，发现了原因是因为在从左到右枚举时，dp[5]已经被覆盖了，此时的dp[5]表示的含义是，当余量为5时，放入前两件物品的最大价值（等价于dp[2][5]），而dp[5]应该表示的真实含义是，当余量为5时，放入第一件物品的最大价值（等价于dp[1][5]）。

也就是说从左到右枚举时，左边的数据都是脏数据（指被覆盖的数据），而右边的数据都是干净的数据，而每次计算时又会用到其左边的数据和其本身，因此会出现问题。而从右向左枚举时，右边的数据都是脏数据，而左边的数据都是干净的，因此没有问题。所以枚举必须要从右向左枚举！以下是一个图解：

思考：对于完全背包问题，如果采用一维数组，则对V的枚举需要从左到右枚举。

其原因是因为按照其状态转移方程：

这个时候我们可以看到，当计算dp[i][v]时，需要用到的数据是它左边的数据和它正上方的数据：

dp[i][v]表示的含义是不取第i个元素（此时剩余容量为v）和取第i个元素（此时剩余容量为v - w[i]）的最大值，而v - w[i] 是需要事先就被计算好的（并且是需要脏数据，否则表示的含义是，在v-w[i]的空间中放置第i-1个元素的最大值），因此需要从左到右枚举。