【算法宇宙——在故事中学算法】背包dp之完全背包问题

这篇具有很好参考价值的文章主要介绍了【算法宇宙——在故事中学算法】背包dp之完全背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

学习者不灵丝相传,而自杖明月相反,子来此事却无得失。

前言

尽管计算机是门严谨的学科,但正因为严谨,所以要有趣味才能看得下去。在笔者的前几篇算法类文章中,都采用了以小故事作为引入的方式来介绍算法,但在回看的时候发现学术味还是太浓了,完全没有想看下去的欲望orz~因此笔者决定改组文章结构,将整个算法都以故事的形式呈现,至少让读者能看下去,希望能帮助到大家!

正文

小明的探险之旅(2)

上文说到小明从家中收拾好装备后,就踏上了茫茫星海的探险征程。在航行了数天后,他到达了第一个星球——食戟之星。这颗星球以昂贵而美味的食物而著称,由于小明实在太饿,他直接钻进了一家自助餐店,想好好的回回血。

小明看着这些食物不禁直流口水:这么多好吃的,都好想吃!可是怎么吃才能吃的最好呢。。(注:小明吃好的标准是吃到的所有食物价格总和最高,也就是最能回本)

(小明思考了一会)

小明:感觉这个问题和我搬装备时候的问题很像,但是这次所有食物都是无限供应的。。先想一想之前用到的转移方程吧!
【算法宇宙——在故事中学算法】背包dp之完全背包问题

那么,之前的装备一种只有一件,而这次的食物有无数件,也就是说,不一定是j-w[i],也可以是j-2w[i],j-3w[i]……所以就是
【算法宇宙——在故事中学算法】背包dp之完全背包问题
可是这样的话,时间复杂度就太大了……就算用了滚动数组优化,也会到达平方级的时间复杂度,还要进行复杂的边界判断……

(小明陷入了苦想,直觉告诉他,这种算法还可以进行优化,但以他的学识,想破脑袋也想不出来。最后,小明只能按照这种算法不停推算,等到推算完,他撑着饥肠辘辘的身体去取餐的时候,却发现已经到了打烊的时间了!小明没办法,只能到街上买了一个手抓饼,一边泪流满面的吃着,一边发誓自己一定要学好算法……)

最后的优化

实际上,小明的直觉很准确,可惜他的智商没有直觉那么强大~那么接下来,我们接手他的思路,看看接下来还有什么能优化的地方。
很显然,这次依然可以用滚动数组优化,但为了展示方便,我们先压缩到i和i-1两行:

黄色块是我们当前要确定的值,即fi,j红色块是根据上面的公式,我们枚举的值,设w[i]=2,则:
【算法宇宙——在故事中学算法】背包dp之完全背包问题
接下来是重点,我们看确定fi,j-2时的表格,黄色块是要确定的值,红色块是枚举的值:
【算法宇宙——在故事中学算法】背包dp之完全背包问题

发现了什么?fi,j-2的值其实就是除了fi-1,j之外的所有红色块的最大值,那么我们可以通过只比较fi,j-2和fi-1,j这两个块的值就可以得出fi,j的值了,即:
【算法宇宙——在故事中学算法】背包dp之完全背包问题
这就是完全背包问题的转移方程。接下来上代码:

代码

#include <iostream>
using namespace std;
const int maxn = 13010;
int n, W, w[maxn], v[maxn], f[maxn];

int main() {
  cin >> n >> W;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; 
  for (int i = 1; i <= n; i++)//循环n次,因为要对n件物品进行选择
    for (int l = w[i]; l <= W; l++)//从前向后更新
      f[l] = max(f[l], f[l - w[i]] + v[i]);//转移方程
  cout << f[W];
  return 0;

最后小记以下笔者在写这篇博客时想到的一个关于边界处理的问题:当l<w[i]时,不可能再取第i件物品,所以不会改变数组中的数据;而一开始由于定义的是全局变量,所以数据都初始化为0,也与如果一直不取物品的话,价值为0的事实相符合,所以不特意处理边界是没问题的。
【算法宇宙——在故事中学算法】背包dp之完全背包问题
我是霜_哀,在算法之路上努力前行的一位萌新,感谢你的阅读!码文不易,如果觉得好的话,可以关注一下,我会在将来带来更多更全面的算法讲解!文章来源地址https://www.toymoban.com/news/detail-419004.html

到了这里,关于【算法宇宙——在故事中学算法】背包dp之完全背包问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法第十五期——动态规划(DP)之各种背包问题

    目录 0、背包问题分类 1、 0/1背包简化版 【代码】 2、0/ 1背包的方案数 【思路】

    2023年04月09日
    浏览(41)
  • 动态规划:完全背包问题----中专生刷算法

    需要基础:闫氏dp分析法,01背包问题 先去看一下01背包问题,再看完全背包 动态规划:选择dp及优化01背包问题-CSDN博客 做过01背包问题的同学会发现,完全背包问题的代码 在01背包基础上改动很小,但是里面的思想,有很大差距 题目 有 N 种物品和一个容量是 V的背包,每种物品

    2024年04月16日
    浏览(48)
  • 力扣刷题-动态规划算法3:完全背包问题

    问题描述: 1)有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 2) 每件物品都有无限个(也就是可以放入背包多次) (比0-1背包多出的条件) 3) 求解将哪些物品装入背包里物品价值总和最大。 求解步骤: 1)首先遍历物品,然

    2023年04月13日
    浏览(58)
  • 算法篇——动态规划 完全和多重背包问题 (js版)

    01 背包 问题和 完全背包 问题的不同点在于,所有的物品只能 使用一次 ,判断  哪些物品  装进背包里 物品价值和 最大;而 完全背包 问题中,所有物品都能 使用n次 ,判断 哪个物品 装 n 个进去 物品价值和 最大。 01 背包的递推公式是: 【当然先遍历物品还是背包的容量

    2024年02月08日
    浏览(46)
  • 算法题打卡day45-背包问题 | 70. 爬楼梯 (进阶)、322. 零钱兑换、279.完全平方数

    70. 爬楼梯 - 力扣(LeetCode) 状态:查看思路后AC。 除了常规的可以爬一或二级台阶,当题目稍微修改一下,变成可以爬m级台阶,之前的DP思路就有局限(dp[i] = dp[i-1] + dp[i-2),为了通杀这类问题,可以将题目转换为完全背包问题,可以爬的楼梯级数就是背包中的物品,楼梯总

    2024年02月11日
    浏览(50)
  • 力扣算法刷题Day44|动态规划:完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目:#518.零钱兑换II(完全背包组合问题) 刷题时长:7min 解题方法:动态规划(完全背包) 复杂度分析 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换:纯完全背包是凑成背包最大价值是多少,而本

    2024年02月13日
    浏览(42)
  • 动态规划DP之背包问题3---多重背包问题

    目录 DP分析: 优化:  二进制优化 例题:         01背包是每个物品只有一个,完全背包问题是每个物品有无限个。         那么多重背包问题就是 每个物品有有限个 。 有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解

    2024年03月20日
    浏览(49)
  • 【动态规划之完全背包问题】完全背包问题的通用解法与优化

    ⭐️ 前面的话 ⭐️ 本篇文章将介绍动态规划中的背包问题——完全背包问题,前面我们已经介绍了0-1背包问题,其实完全背包问题就只改了0-1背包问题的一个条件,即物品可选择次数由一次改为无数次,仅此而已,下面我们就来开始介绍完全背包问题。 📒博客主页:未见

    2023年04月22日
    浏览(50)
  • 背包问题——01背包|完全背包

    目录 前言背包问题的历史  01背包  1、题目 2、暴力解01背包  Ⅰ、代码 3、动态规划解01背包 Ⅰ、二维dp数组解01背包 1)dp数组的含义  2)递推公式  3)dp数组的初始化  4)遍历顺序的讨论  5、代码  Ⅱ、一维数组解01背包  1)一维数组|滚动数组  2)一维数组的含义及递

    2024年02月02日
    浏览(48)
  • 算法竞赛必考算法——动态规划(01背包和完全背包)

    1.1题目介绍 1.2思路一介绍(二维数组) 代码如下: 1.3思路二介绍(一维数组) 空间优化   为什么可以使用一维数组?   我们先来看一看01背包问题的状态转移方程,我们可以发现 f[i]只用到了f[i-1],其他的是没有用到的,我们可以用滚动数组来做。   还有一个原因就是我

    2024年02月02日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包