01背包一维数组推演过程

userId_undefined

Yuilice

倔强青铜

2023-07-29 16:46:06

发布于：广东

21阅读
0回复
0点赞

// 设定背包体积为V
// 物品的体积为w[i],价值为v[i]
// 我们设定当前枚举的背包体积为j的时候

// 当我们枚举到物品i的时候，只要物品体积w[i] > j 的时候
// 就意味着当前物品无法存放至背包，这时候只能选取不拿
// 只需要继承上一次计算的数值即可
// 而我们真正需要计算的背包体积范围只有 w[i] ~ V;

//设定dp[j] 为背包体积为j的情况下存储的最大价值
// j >= w[i] max{dp[j],dp[j-w[i]]+v[i]}
// dp[j]意为不拿的价值 dp[j-w[i]] + v[i] 计算拿取物品剩余体积的最大价值
// 加上物品价值

userId_undefined
去预览
0/2000

全部评论 2

热门讨论