01背包问题(二)

无道 2019-06-12 0 条评论 算法分享 阅读622 手机阅读

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])
全文完 [
有帮助?打赏
支付宝打赏
微信打赏
]
标签: 背包问题
修改: 2019-06-12 10:49
这篇文章还没有评论呢~
点击刷新/生成验证码
It's me
昵称:无道
坐标:成都
性别:
一个人,一介学生,一个儿子~ 愿你我都被世界温暖以待
迷思爱 公众号

新建了个公众号,会不定期分享一些小玩意,有提升效率的办公软件、有一些黑科技的软件、或教程等等。

爷~,要不关注下~~