01背包问题（二）

01背包的时间复杂度很难再降低了，但空间复杂度还能进行优化，可以把数组从二维降到一维。

截图-1560306959

如上图所示，01背包的两重for循环是无法降低了，

但是空间复杂度是O(MN)却是可以降成O(N)的。

如果我们从大到小遍历，即从v -> 0，我们仍只需知道第i-1物品的状态。

因此我们可以优化转移方程为value[j] = max(value[j], value[j - v[i]] + w[i]);将复杂度降为O(v)。

如下所示

for (int i = 1; i <= N; ++i) { // i循环物品数量
    for (int j = V; j >= v[i]; --j) { // j循环背包容量
        // 这里要j >= v[i] 也就是背包容量j要大于该物品所需容量
        if (j >= v[i])
            // 这种题，一点小失误都会导致失败，这里要加=
            value[j] = max(value[j], value[j - v[i]] + w[i]);
    }
}

需要注意的是，第二重for循环是逆序的。

以下摘自博客：https://blog.csdn.net/zonahaha/article/details/81168244

从空间花费从大到小来构成for循环的话，就可以直接用一维数组来保存物品数-1 的值。

当背包容量为j时，已经放入了i件物品，最大价值为d[j]

当第i件物品比背包容量还大时，d[j]=d[j];

当第i件物品比背包容量小时，就要判断两种情况：

• 不放的话，和上式相同。
• 放的话，背包容量-第i件物品的质量再去装前i-1件物品，所得得最大价值加上第i件物品的价值，两者较大值即为最优解。d[j]=max(dp[j],dp[j-w[i]]+v[i])