算法萌新如何学好动态规划（3）( 三 )
。 而在我们更新完
文章插图
后 ，
文章插图
的值即变为
文章插图
的值 ， 由此我们大大降低了该算法的空间开销 ， 这种空间优化方法叫做「滚动数组」 。
完全背包了解完「0/1 背包」模型后 ， 我们继续介绍「完全背包」模型 ， 其基本问题如下所示：
一共有 N 类物品 ， 其中第 i 类物品的体积为
文章插图
， 价值为
文章插图
， 且每类物品可以选无数个 。 现要求选择一些物品放入一个容积为 M 的背包中 ， 使得物品总体积不超过 M 的前提下 ， 物品总价值最大 。
不难发现 ， 「完全背包」与「0/1 背包」最大的差别就在于每一类物品可以选多少个 ， 其中「完全背包」每一类物品可以选无数个 ， 而「0/1 背包」中每一类物品只能选 1 个 。
了解完模型差异后 ， 我们继续思考如何解决该问题 。 与「0/1 背包」模型比较类似 ， 本问题也只有三个参数 ， 分别是物品编号、物品体积以及物品价值 。 因此我们可以照搬「0/1 背包」的「DP 状态」 ， 即
文章插图
表示仅考虑前 i 类物品 ， 所选物品总体积为 j 时的最大物品总价值 。
由于每一类物品可以选无数次 ， 因此对于
文章插图
来说 ， 如果不取则
文章插图
， 如果取一个则
文章插图
， 如果取两个则
文章插图
， 如果取 x 个则
文章插图
。
因此我们可以得到
文章插图
但这样的话我们就需要不断遍历 x ， 显然会导致时间复杂度过高 ， 因此我们还可以继续优化 。
文章插图
又因为
文章插图
因此只要正序遍历 j ， 即保证求取
文章插图
时 ，
文章插图
已经得到 ， 「DP 转移方程」就可以优化为
文章插图
对比「0/1 背包」中
文章插图
推荐阅读
- 大一非计算机专业的学生，如何利用寒假自学C语言
- 向日葵远程控制企业版客户端更新升级，优化远控UI适配SADDC内核算法
- 红米K40渲染图曝光：居中挖孔+后置四摄，这外观你觉得如何？
- 奋斗|该如何看待拼多多员工猝死：鼓励奋斗，也要保护好奋斗者
- 装机点不亮 如何简易排查硬件问题？
- 虾米音乐宣布关停！我的歌单如何导入QQ音乐、网易云音乐？
- 人脸识别设备主板如何选型 软硬整合大幅缩短开发时间
- Mini-LED产品效果究竟如何？
- 专家介绍如何判断智能手机被入侵：运行速度变慢、电池消耗过快以及卡顿
- 在谷歌算法更新之后2020年盗版网站流量锐减三分之一