不止一个背包的背包问题_算法基础课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/168869.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • 初识.Net审计

    初识.Net审计前言对.net认知比较少,学习一下.net的一些简单审计。遇到.net源码能简单审审。基础概念文件类型ASPX.cs是页面后的代码,aspx负责显示,服务器端的动作就是在as

    2021年12月13日
  • docker 镜像构建_dockerfile引入两个镜像

    docker 镜像构建_dockerfile引入两个镜像前言如果我们已经安装了一个python3的环境,如果另一台机器也需要安装同样的环境又要敲一遍,很麻烦,这里可以配置Dockerfile文件,让其自动安装,类似shell脚本Dockerfile编写

  • 解决document.cookie无法获取到cookie问题

    解决document.cookie无法获取到cookie问题一、前言在进行前后端联调的时候,由于想实现一个登出操作,前端自动删除浏览器存储的cookie,想通过document.cookie来获取进而进行删除操作,但是发现浏览器有cookie;但是无法获取到情况遂记录二、场景复现首先登录后,浏览器中是有记录cookie的,如图然后我代码层执行documen.cookie发现获取不到,浏览器控制台也同样后面去研究了一下application中存放的cookies的属性内容,发现有个属性HttpOnly是选中状态,这个状态是由于后端设置cookie的时候

  • 实现watch命令

    实现watch命令

  • clearfix_Clear クリア

    clearfix_Clear クリア.clearfix:after{content:”.”;display:block;height:0;clear:both;visibility:hidden;}.clearfix{display:inline-block;}/*HidesfromIE-mac\*/*html.clearfix{he

    2022年10月21日
  • 解决SecureCRT中文显示乱码

    解决SecureCRT中文显示乱码

发表回复

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

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