10800 01背包问题（关于空间优化）

好的，谢谢老师

另外，这种对于某道题目的提问，可以到对应题目的题目板块讨论区去发帖哦。

解释

这里从 到 仅仅是为了避免重复更新，你可以看到如果是二维数组的写法，从 到 循环也是可以的。 这是因为去掉一维以后，如果你从 到 的话，你刚才更新过的值，可能马上就去更新别的值去了，这样一次循环内，你其实更新了很多轮的值。
而从 到 的顺序更新，可以保证每一次循环内，只更新了一轮的值。

例子

比如只有 个物品，价值和体积都是 ，背包的空间是 ，如果只用一维数组 f[] 计算：

• 初始时

f[0]=0  
f[1]=0
f[2]=0
f[3]=0

如果是从 到 循环的话：

• i=1的循环

f[0]=0
f[1]=max(f[1],f[0]+1)=1
f[2]=max(f[2],f[1]+1)=2
f[3]=max(f[3],f[2]+1)=3

这里就已经不对了，因为你在一次循环内用更新过的值又去更新了别的值。

如果是从 到 循环的话：

• i=1的循环

f[3]=max(f[3],f[2]+1)=1
f[2]=max(f[2],f[1]+1)=1
f[1]=max(f[1],f[0]+1)=1
f[0]=0

这样才是正确的。

补充

如果一定想从 到 循环的话，可以使用 滚动数组 这种方法。
数组开成 f[V][2] 的，用变量 cur 和 pre 表示当前要更新的是哪一维、上次更新的是哪一位（取值 或 ），然后每次更新的时候写成：

for i=1..N
    for v=0..V
        f[v][cur]=max{f[v][pre],f[v-c[i]][pre]+w[i]};

然后把 cur 和 pre 交换就行。（初始取值可以是 cur = 1, pre = 0）