背包DP

完全背包:每个物品可以选无数次。


\(n\):物品的总个数。


\(W\):背包的最大总容量


\(w[i]\):第 i 件物品的重量/体积


\(v[i]\):第 i 件物品的价值 (value)。


\(dp[j]\):当容量限制为 j 时,能获得的最大价值。

当我们计算
\(dp[j]\) 时,我们希望
\(dp[j – w]\) 是可能已经放入了第 i 个物品的状态.

赞(0)
未经允许不得转载:小狮博客 » 背包DP
分享到: 更多 (0)

联系我们