动态规划之多重背包模型

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

前置知识: 

01背包问题:动态规划之01背包模型_如何何何的博客-CSDN博客

完全背包问题:动态规划之完全背包模型_如何何何的博客-CSDN博客

多重背包问题:

给定一个有一定容量的背包,和 n 个物品,每个物品有 si 件;

每个物品有其对应的体积和价值;

问背包最多能装下的物品的最大价值为多少。

输入格式:

第一行两个整数,N,V,分别表示物品数量和背包容积;

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

输出格式:

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

思路:

每件物品的数量是有限的,并且各不相同。并不能和完全背包问题一样优化;

如果数据范围比较小,可在01背包的基础上加上第三重循环(枚举选几件该物品);

故可以将01背包当做特殊的多重背包来处理。

代码模板如下:

//一维
#include<iostream>
using namespace std;

const int N = 110;
int f[N][N];
int n, m;//n件物品,容量是m

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

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

        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];//不选
            for (int k = 0; k <= s; k++)//选k件
                if (k * v <= j)f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w);
        }
    }

    cout << f[n][m];

    return 0;
}

//一维
#include<iostream>
using namespace std;

const int N = 110;
int f[N];
int n, m;//n件物品,容量是m

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

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

        for (int j = m; j >= v; j--) {
            for (int k = 0; k <= s; k++)//选k件
                if (k * v <= j)f[j] = max(f[j], f[j - k * v] + k * w);
        }
    }

    cout << f[m];

    return 0;
}

二进制优化:

将每一类物品打包成2^0、2^1、2^2 …… 这样的logn堆物品;

将这些物品进行组合就可以组合出1~n内的任何数量的该物品;

即将所有分好的物品堆进行01背包处理就可以枚举出所有情况。

代码模板如下:
 

#include<iostream>
using namespace std;

const int N = 2010;
int f[N];
int w[N * N], v[N * N], cnt = 0;//最多1000*logn堆物品
int n, V;

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

    int v1, w1, s;
    for (int i = 0; i < n; i++) {//打包
        cin >> v1 >> w1 >> s;
        int k = 1;
        while (s) {
            if (s >= k) {
                v[cnt] = k * v1;
                w[cnt++] = k * w1;
                s -= k;
            }
            else {
                v[cnt] = s * v1;
                w[cnt++] = s * w1;
                s = 0;
            }
            k *= 2;
        }
    }

    for (int i = 0; i <= cnt; i++)//01背包
        for (int j = V; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[V];
    return 0;
}

例题1 . 庆功会:

信息学奥赛一本通T1269-庆功会 - C语言网 (dotcpp.com)

多重背包裸题,默写多重背包模板即可。文章来源地址https://www.toymoban.com/news/detail-472742.html

AC代码如下:

#include<iostream>
using namespace std;

const int N = 6010;
int v[N], w[N], cnt = 0;
int f[N];
int n, V;

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

    int v1, w1, s;
    for (int i = 0; i < n; i++) {
        cin >> v1 >> w1 >> s;
        int k = 1;
        while (s) {
            if (s >= k) {
                v[cnt] = k * v1;
                w[cnt++] = k * w1;
                s -= k;
            }
            else {
                v[cnt] = s * v1;
                w[cnt++] = s * w1;
                s = 0;
            }
            k *= 2;
        }
    }

    for (int i = 0; i < cnt; i++)
        for (int j = V; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[V];

    return 0;
}

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

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

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

相关文章

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

    有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 s i 件,每件体积是 v i ,价值是 w i 。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 用下面这个图来分别动态规划的四个经典背包问题 定义状态的含义(这一步需要

    2023年04月08日
    浏览(41)
  • 【算法日志】动态规划刷题:01背包问题,多重背包问题(day37,day38)

    目录 前言 目标和(01背包) 一和零(01背包) 零钱兑换(多重背包) 排列总和(多重背包) 这两天都是背包问题,其中的01背包的一些应用问题需要一定的数学建模能力,需要i将实际问题简化成我们熟悉的背包问题;而这两天的多重背包问题还算比较基础,但也要我明白了

    2024年02月11日
    浏览(56)
  • 算法 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日
    浏览(60)
  • 动态规划之二维费用的背包模型

    前置知识: 01背包问题:动态规划之01背包模型_如何何何的博客-CSDN博客 完全背包问题:动态规划之完全背包模型_如何何何的博客-CSDN博客 多重背包问题:动态规划之多重背包模型_如何何何的博客-CSDN博客 二维费用即背包问题有两个限制条件。 例题: 有 N 件物品和一个容

    2024年02月15日
    浏览(42)
  • LeetCode264. 丑数 II(相关话题:多重指针动态规划)

    给你一个整数  n  ,请你找出并返回第  n  个  丑数  。 丑数  就是质因子只包含  2 、 3  和  5  的正整数。 示例 1: 示例 2: 提示: 1 = n = 1690 动态规划数组:dp 数组用于存储从第 1 个到第 n 个丑数。dp[0] 初始化为 1,因为第一个丑数定义为 1。 三个指针:p2、p3、p5 分

    2024年01月20日
    浏览(42)
  • 动态规划-背包问题-完全背包

    对比01背包,完全背包中的每件物品有无数件。 也就是说,每件物品可以拿0,1,…,k,…件。 dp[i][j]表示前i种物品,体积为j时的最大价值 对于第i件物品: 不拿:dp[i][j]⇐dp[i-1][j] 拿一件:dp[i][j]⇐dp[i-1][j-w[i]]+v[i] 拿两件:dp[i][j]⇐dp[i-1][j-2w[i]]+2v[i] … 拿k件:dp[i]][j]⇐dp[i

    2024年04月08日
    浏览(49)
  • 动态规划之背包问题——完全背包

    算法相关数据结构总结: 序号 数据结构 文章 1 动态规划 动态规划之背包问题——01背包 动态规划之背包问题——完全背包 动态规划之打家劫舍系列问题 动态规划之股票买卖系列问题 动态规划之子序列问题 算法(Java)——动态规划 2 数组 算法分析之数组问题 3 链表 算法

    2024年02月03日
    浏览(63)
  • 动态规划——01背包和完全背包

    目录 01背包模型 题目  dp   滚动数组优化 第一问  第二问  扩展 完全背包 题目  动态规划​编辑  滚动数组优化  关于-1的代码层面优化 💰🪙 背包就是有限制条件的组合问题 有一个背包能容纳的体积是v,现在有n个物品,第i个物品的体积为vi,价值为wi。 (1)求这个背包

    2024年01月20日
    浏览(41)
  • 【动态规划专栏】-- 01 背包问题 -- 动态规划经典题型

    目录 背包问题概述 01 背包问题 01背包⭐⭐  【算法原理】 第一问 第二问 C++ 算法代码 复杂度分析 【空间优化 - 滚动数组】 C++ 算法代码 复杂度分析 分割等和子集⭐⭐ 【算法原理】  对于类01背包问题 C++ 算法代码  【空间优化 - 滚动数组】  C++ 算法代码 目标和⭐⭐ 【算

    2024年02月05日
    浏览(56)
  • 【笔记】动态规划(1)---01背包和完全背包

    集合:选法集合 属性:最优选择 集合的划分 状态表示 集合:所有只考虑 第i个物品前的 且总体积不大于j的所有 选法 。 属性:在所有集和中, 价值最大的选法 。 状态计算 集合的划分:总是在(第 i - 1个) 状态最优时,计算 第 i 个状态。 背包已经最优,故对于任意容积

    2024年02月02日
    浏览(67)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包