0-1多重背包(单调队列+多重背包)[通俗易懂]

0-1多重背包(单调队列+多重背包)[通俗易懂]原题链接有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。输入格式第一行两个整数,N,V (0<N≤1000, 0<V≤20000),用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。输出格式输出一个整数,表示最大价值。数据范围0<N≤1

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接
有 N 种物品和一个容量是 V 的背包。

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

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

输入格式
第一行两个整数,N,V (0<N≤1000, 0<V≤20000),用空格隔开,分别表示物品种数和背包容积。

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

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

数据范围
0<N≤1000
0<V≤20000
0<vi,wi,si≤20000
提示
本题考查多重背包的单调队列优化方法。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例:

10

题解
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int g[N],q[N],f[N];
int main(){ 
   
    int n,m;
    cin>>n>>m;
    int v,w,s;
    for(int i = 0;i < n;i ++){ 
   
        cin>>v>>w>>s;
        memcpy(g, f, sizeof g);
        for(int j = 0;j < v;j ++){ 
   
            int tt = 0,hh = 0;
            for(int k = j;k <= m;k += v){ 
   
                if(hh < tt && q[hh] < k - s * v)hh ++;
                while(hh < tt && g[k] - (k - j) / v * w >= (g[q[tt - 1]] - (q[tt - 1] - j) / v * w))tt -- ;
                q[tt ++] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168742.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 热插拔——矿机先行利器[通俗易懂]

    热插拔——矿机先行利器[通俗易懂]IPFSFilecoin上线在即,准备挖矿的小伙伴们已近磨刀霍霍了,都在积极选择自己心仪的矿机。但是如今市场上矿机众多,对于矿机的配置也是众说纷纭,相信许多的小伙伴也是十分茫然,当然,星际魔方今天只谈专业IPFS矿机,家用电脑组装的矿机我们后期再谈。工欲善其事,必先利其器。Fliecoin挖矿就是一种优质资源竞争的行为。形象理解就类似于嘀嘀打车,一个人想去另一个地方,在滴滴下单,司机开始抢单…

  • RJ45 网线接口介绍

    RJ45接口通常用于数据传输,最常见的应用为网卡接口。  RJ45是各种不同接头的一种类型(例如:RJ11也是接头的一种类型,不过它是电话上用的);RJ45头根据线的排序不同,分为有两种,一种是橙白、橙、绿白、蓝、蓝白、绿、棕白、棕;另一种是绿白、绿、橙白、蓝、蓝白、橙、棕白、棕;因此使用RJ45接头的线也有两种即:直通线、交叉线。RJ45型网卡接口  10100basetxRJ

  • 理解条件概率_如何理解条件概率

    理解条件概率_如何理解条件概率版权声明:本文为博主原创文章,未经博主同意不得转载。https://blog.csdn.net/sheismylife/article/details/25009545网上看了一些解释。认为这个比

  • 函数类型_C语言函数类型

    函数类型_C语言函数类型函数类型在ECMAScript中有三种函数类型:函数声明,函数表达式和函数构造器创建的函数。每一种都有自己的特点。1.函数声明这种函数类型的主要特点在于它们仅仅影响变量对象。该特点也解释了第二

  • css学习记录九:元素属性解释(五):opacity 属性

    css学习记录九:元素属性解释(五):opacity 属性css学习记录九:元素属性解释(五):opacity属性一、opacity属性一、opacity属性改变盒子的透明度opacity=“0.5”0是完全透明。1是不透明会继承给子元素rgba不会继承

  • Mac os 安装Python Pycharm 配置环境「建议收藏」

    Mac os 安装Python Pycharm 配置环境「建议收藏」  主要就是这三个库的安装   importrequestsfrombs4importBeautifulSoupimporttime我是PYthon小白,自己把程序运行出来在环境配置走了不少弯路。因为我还安装了一台Windows环境,中间交叉做了其他一些事情,所以思路没有那么清晰。但是刚刚终于成功抓了数据。代码和程序运行成功截图放在最后。先说说环境配置,我会尽量回忆。我安装的是…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号