蓝桥杯算法全集之多重背包问题I(动态规划算法)

这篇具有很好参考价值的文章主要介绍了蓝桥杯算法全集之多重背包问题I(动态规划算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

蓝桥杯算法全集之多重背包问题I(动态规划算法)

一、概念定义

N 种物品和一个容量是 V 的背包。
i种物品最多有 s i 件,每件体积是 v i,价值是 w i
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

用下面这个图来分别动态规划的四个经典背包问题

蓝桥杯算法全集之多重背包问题I(动态规划算法)

二.动态规划的核心步骤

  1. 定义状态的含义(这一步需要一定的做题经验的积累)

  1. 状态的转化,建立前后状态的等式关系(一般通过最后一步分类讨论来进行状态计算)

  1. 精准定义初始值文章来源地址https://www.toymoban.com/news/detail-404312.html


三:题目描述

N 种物品和一个容量是 V 的背包。

i 种物品最多有 si 件,每件体积是 vi,价值是 wi

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

输出最大价值。

输入格式

第一行两个整数,NV,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤100

0<vi,wi,si≤100

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例、

10

四.思路分析

和前一篇完全背包问题的解法几乎一致,区别在于这里的物品的数量是有限制的,其实也很简单,答题思路一致,只需要加一个限制条件k <= s【i】就可以,s【i】指的是第i个物品的数量

根据上述的动态规划的步骤我们一步一步来思考:

  1. 定义状态的含义

f【i,j】:从前i个物品中选,且最大体积不超过j的选法的集合
  1. 状态计算

既然是从前i个物品当中选, 最后一步一定是决定 选几个第i个物品(这里不同于01背包问题)
a. 选取0个第i个物品=====>f【i,j】= f【i - 1,j 】
b.选取1个第i个物品=====>f【i,j】= f【i - 1,j - v【i】】+w【i】
c.选取2个第i个物品=====>f【i,j】= f【i - 1,j - 2v【i】】+ 2w【i】
d.选取3个第i个物品=====>f【i,j】= f【i - 1,j - 3v【i】】+3w【i】
·
·
·
k.选取k个第i个物品=====>f【i,j】= f【i - 1,j - kv【i】】+k*w【i】
  1. 精准定义初始值

这里的初值都是0,没必要修改。但是有些题目的初值是比较重要的。
比如青蛙跳级题目 剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣(LeetCode)

五:万年无误代码模板(含思路解析)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N]; // s数组是存储第i个物品的数量
int f[N][N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ ) // 取k个物品的体积不能超过j,且k的物品不可能超过该物品的数量
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

    cout << f[n][m] << endl;
    return 0;
}

到了这里,关于蓝桥杯算法全集之多重背包问题I(动态规划算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 三十八、动态规划——背包问题( 01 背包 + 完全背包 + 多重背包 + 分组背包 + 优化)

    0 1 背包问题: 条件:N 个物品容量为 V 的背包,每件物品最多用 1 次,其中物品信息体积为 Vi,价值为 Wi。 目标:选出物品,使价值最大(不一定装满背包)。 特点:每件物品 最多只用 1 次 完全背包问题: 特点:每一件物品都有 无限个 多重背包问题: 特点:每个物品

    2024年02月07日
    浏览(53)
  • 算法 DAY45 动态规划07 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包

    和377. 组合总和 Ⅳ (opens new window)基本就是一道题了。 本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包 动态规划五部曲 1、确定dp[j]的含义 dp[j] 凑成 j 的最少硬币的个数 2、确定递推公式 比如想凑成3, 如果手里有1,那么最小个数就是dp[2]+1 如果手里有2,那

    2024年02月02日
    浏览(61)
  • 动态规划之多重背包模型

    前置知识:  01背包问题:动态规划之01背包模型_如何何何的博客-CSDN博客 完全背包问题:动态规划之完全背包模型_如何何何的博客-CSDN博客 给定一个有一定容量的背包,和 n 个物品,每个物品有 si 件; 每个物品有其对应的体积和价值; 问背包最多能装下的物品的最大价值

    2024年02月08日
    浏览(54)
  • 算法系列--动态规划--背包问题(3)--完全背包介绍

    💕\\\"Su7\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(3)–完全背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(3)--完全背包介绍 链接: 完全背包 可以发现完全背包问题和01背包问题还是特比相似的 分析: 完全背包问题 是 01背包问题 的推广

    2024年04月25日
    浏览(45)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(55)
  • 【算法-动态规划】0-1 背包问题

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月08日
    浏览(46)
  • 算法学习17-动态规划01:背包问题

    提示:以下是本篇文章正文内容: 提示:这里对文章进行总结: 💕💕💕

    2024年04月27日
    浏览(52)
  • C++ DP算法,动态规划——背包问题(背包九讲)

    有N件物品和一个容量为 V V V 的背包。放入第i件物品耗费的空间是 C i C_i C i ​ ,得到的价值是 W i W_i W i ​ 。 求解将哪些物品装入背包可使价值总和最大。 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即 F [ i , v ] F[i, v] F

    2024年02月16日
    浏览(50)
  • acwing算法基础之动态规划--背包问题

    (零) 背包问题描述:有 N N N 个物品,每个物品的体积是 v i v_i v i ​ ,价值是 w i w_i w i ​ ,现有容量是 V V V 的背包,求这个背包能装下的物品的最大价值。 01背包问题:每个物品只有1个。 完全背包问题:每个物品有无穷多个。 多重背包问题:第 i i i 个物品有 s i s_i s

    2024年02月05日
    浏览(47)
  • 【动态规划】01背包问题——算法设计与分析

    若超市允许顾客使用一个体积大小为13的背包,选择一件或多件商品带走,则如何选择可以使得收益最高? 商品 价格 体积 啤酒 24 10 汽水 2 3 饼干 9 4 面包 10 5 牛奶 9 4 0-1 Knapsack Problem 输入: quad - n n n 个商品组成集合 O O O ,每个商品有属性价格 p i p_i p i ​ 和体积 v i v_i v

    2024年02月04日
    浏览(79)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包