算法萌新如何学好动态规划（3）( 四 )
， 「完全背包」由于每类物品可以取多次 ， 因此转移方程变为
文章插图
， 具体代码如下所示 。
int DP() {for(int i = 1; i <= M; i++)f[0][j] = -inf; // 负无穷 ， inf 可以为 1e8f[0][0] = 0;for(int i = 1; i <= N; i++)for(int j = 0; j <= M; j++)if(j >= v[i])f[i][j] = max(f[i-1][j], f[i][j-v[i]] + w[i]);elsef[i][j] = f[i-1][j];int ans = 0;for(int i = 0; i <= M; i++)ans = max(ans, f[N][i]);return ans;}根据之前介绍的「滚动数组」方法 ， 我们可以将上述代码优化为：
int DP() {for(int i = 1; i <= M; i++)f[j] = -inf; // 负无穷 ， inf 可以为 1e8?f[0] = 0;for(int i = 1; i <= N; i++)for(int j = v[i]; j <= M; j++)f[j] = max(f[j], f[j-v[i]] + w[i]);int ans = 0;for(int i = 0; i <= M; i++)ans = max(ans, f[i]);return ans;}?多重背包最后我们来介绍「多重背包」模型 ， 其基本问题如下所示：
一共有 N 类物品 ， 其中第 i 类物品的体积为
文章插图
， 价值为
文章插图
， 且每类物品只有
文章插图
个
文章插图
。 现要求选择一些物品放入一个容积为 M 的背包中 ， 使得物品总体积不超过 M 的前提下 ， 物品总价值最大 。
将该问题与「0/1 背包」模型进行对比 ， 可以发现唯一差别在于「0/1 背包」中每一类物品的
文章插图
， 因此我们可以考虑如何将「多重背包」转换为「0/1 背包」进行求解 。
首先比较容易想到的是 ， 我们可以进行暴力拆分 ， 即将每一类物品拆分为
文章插图
个 ， 总物品数量从 N 变为
文章插图
， 因此我们可以直接使用「0/1 背包」模型进行解决 ， 具体代码如下所示：
int DP() {for(int i = 1; i <= M; i++)f[j] = -inf; // 负无穷 ， inf 可以为 1e8f[0] = 0;for(int i = 1; i <= N; i++)for(int k = 1; k <= c[i]; k++)for(int j = M; j >= v[i]; j++)f[j] = max(f[j], f[j-v[i]] + w[i]);int ans = 0;for(int i = 0; i <= M; i++)ans = max(ans, f[i]);return ans;}直接暴力拆分使得该问题变得简单 ， 但是时间复杂度却显著增加 ， 为
文章插图
。 于是我们需要思考有没有什么方法可以对该问题进行优化？
?答案显然是有的 ， 即对每一类物品进行二进制拆分 。 首先回顾计算机中二进制的知识 ， 即从
文章插图
这 k 个数字中选取若干个相加 ， 可以表示出
文章插图
中的任何整数 。
推荐阅读
- 大一非计算机专业的学生，如何利用寒假自学C语言
- 向日葵远程控制企业版客户端更新升级，优化远控UI适配SADDC内核算法
- 红米K40渲染图曝光：居中挖孔+后置四摄，这外观你觉得如何？
- 奋斗|该如何看待拼多多员工猝死：鼓励奋斗，也要保护好奋斗者
- 装机点不亮 如何简易排查硬件问题？
- 虾米音乐宣布关停！我的歌单如何导入QQ音乐、网易云音乐？
- 人脸识别设备主板如何选型 软硬整合大幅缩短开发时间
- Mini-LED产品效果究竟如何？
- 专家介绍如何判断智能手机被入侵：运行速度变慢、电池消耗过快以及卡顿
- 在谷歌算法更新之后2020年盗版网站流量锐减三分之一