闫学灿acwing_分组背包问题

闫学灿acwing_分组背包问题有 N 种物品和一个容量是 V 的背包。物品一共有三类:第一类物品只能用1次(01背包);第二类物品可以用无限次(完全背包);第三类物品最多只能用 si 次(多重背包);每种体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。si=−1 表示第 i 种

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

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

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

物品一共有三类:

第一类物品只能用1次(01背包);
第二类物品可以用无限次(完全背包);
第三类物品最多只能用 si 次(多重背包);
每种体积是 vi,价值是 wi。

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

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

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

si=−1 表示第 i 种物品只能用1次;
si=0 表示第 i 种物品可以用无限次;
si>0 表示第 i 种物品可以使用 si 次;
输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000

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

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

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

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

(0)


相关推荐

  • 高等数学学习目录

    高等数学学习目录第一章函数与极限第一节映射与函数初等函数双曲函数第二章导数的概念基本初等函数的倒数导数的四则运算第四章不定积分不定积分概念与性质天子骄龙

  • 在线java学习_Java在线学习「建议收藏」

    在线java学习_Java在线学习「建议收藏」分阶段进阶教学+阶段考评让学习无死角因为考虑学员基础水平参差不齐,所以动力节点的课程安排对学员进行科学细致的划分,整个教学安排共分两大部分即:基础部分和就业部分,基础部分课程由教学总监定制最适合零基础入门的课程大纲;就业部分课程由教研部实地探访名企如百度、京东、新浪等企业,将最前沿的技术引入到课堂,同时又根据就业课程的深度不同划分为7个阶段,每个阶段都有不同的技术侧重点,层层深入。纵观来看,动力…

  • linux opera flash插件,Linux下64位的Firefox、Opera浏览器安装Flash插件

    linux opera flash插件,Linux下64位的Firefox、Opera浏览器安装Flash插件Linux下,64位的Firefox、Opera等浏览器默认搜索到的Flash插件是32位的,安装之后也不能正常工作。需要手工安装一下。1.下载插件使用浏览器下载:到Adobe的站点上下载64位的Flash插件:http://labs.adobe.com/downloads/flashplayer10_square.html插件下载地址:http://download.macromedia.co…

  • php小程序接口开发_微信小程序登录流程

    php小程序接口开发_微信小程序登录流程微信小程序调用PHP后台接口,解析纯html文本,效果图片预览1、微信js动态传参:wx.request({url:’https://m.****.com/index.php/Home/Xiaoxxf/activity_detail?a_id=’+options.id,//含富文本htmldata:{is_detail:1},method:’GET’,//OPTIONS,GET,HE…

  • 提升苹果电脑速度的10个小技巧[通俗易懂]

    提升苹果电脑速度的10个小技巧[通俗易懂]众所周知,随着时间的流逝,包括Mac在内的所有计算机的速度都会降低。除了换电脑,还是有许多简单的调整可以提高计算机的性能并加快运行速度较慢的Mac,而且这些调整不会花费一分钱。1.升级macOS许多人仍然相信操作系统升级的神话总是会降低计算机的速度。尽管有时它们在旧Mac可能会出现性能问题,但这些更新通常弊大于利。它们包括错误修复,修补程序和改进,这些改进通常会提高Mac的速度。这些操作系统更新文件可能很大。因此,如果硬盘驱动器空间不足,则可能需要先释放硬盘空间。2.释放硬盘空间当您的存储驱动器达到其

  • Python 换行符以及如何在 Python 输出时不换行

    Python 换行符以及如何在 Python 输出时不换行Python中的换行符用于标记行的结尾和新行的开始。如果你想将输出打印到控制台并使用文件,那么你非常需要知道如何使用它。在本文中,你将学习:如何在Python中识别换行符 如何在字符串和打印语句中使用换行符 如何编写不会在字符串末尾添加换行符的打印语句我们开始吧!✨????换行符Python中的换行符是:它包含两个字符:一条反斜线 字母n如果你在字符串中看到此字符,则表示当前行在该点结束,并在其后立即开始新行:你也可以在格式化字符串(f-stri…

    2022年10月21日

发表回复

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

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