当前位置:   article > 正文

背包问题(01背包+完全背包)的一维+二维解法_完全背包二维写法

完全背包二维写法

一、背包问题一维+二维解法

在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

二、背包问题注意点:

1 . dp数组含义:

(1)01背包:往容量为j的背包放入前i个物品,所能获得的最大价值(一个物品只能放入一次
(2)完全背包:往容量为j的背包放入前i个物品,所能获得的最大价值(一个物品可以放入多次

2. 初始化:

(1)完全背包(二维)初始化时,dp[0][j] = Math.floor(j / weight[0]) * value[0]

3. 递推公式:

一维:
(1)01背包:dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
(2)完全背包:dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
二维:
(1)01背包:
放不下:dp[i][j] = dp[i - 1][j]
放得下(放 or 不放):dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
(2)完全背包:
放不下:dp[i][j] = dp[i - 1][j]
放得下(放 or 不放):dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

4. 遍历顺序

一维:
(1)01背包:必须先物品后背包(如果先背包后物品,背包永远只放入一个物品),且背 包倒序遍历(如果正序,一个物品会被放入多次)
(2)完全背包:先物品后背包(反过来也可),正序遍历
二维:
(1)01背包:先物品后背包(反过来也可),正序遍历
(2)完全背包:先物品后背包(反过来也可),正序遍历

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/466287
推荐阅读
相关标签
  

闽ICP备14008679号