不止一个背包的背包问题_分组背包问题

不止一个背包的背包问题_分组背包问题有 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/169153.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • 字符串分割与拼接「建议收藏」

    字符串分割与拼接「建议收藏」.字符串分割与拼接//@””   空的字符串对象     ——-分割     NSString * ptr = @”I am a man”;     NSArray * array = [ptr componentsSeparatedByString:@” “];//将字符串整体作为分割条件 返回值为NSArray不可变数组     NSMutableArray * array1 = 

  • 安卓设备数据转移到ios设备

    安卓设备数据转移到ios设备下载“转移到iOS”,将iPhone和安卓设备插入电源,开启安卓设备的Wi-Fi。安卓设备的数据怎么转移到iPhone设备?点击“从安卓设备转移数据”安卓设备的数据怎么转移到iPhone设备?-在安卓设备上,打开“转移到iOS”应用并轻点“继续”。阅读显示的条款和条件。轻点“同意”以继续,然后轻点“查找代码”屏幕右上角的“下一步”。-在iOS设备上,轻点“从安卓设备转移数据”屏幕…

  • task scheduler服务启动后停止.解决方法_windows创建定时任务

    task scheduler服务启动后停止.解决方法_windows创建定时任务WindowsTaskScheduler使用户可以在此计算机上配置和计划自动任务,同时托管多个Windows系统关键任务。

    2022年10月11日
  • vsftp搭建_安装vsftpd

    vsftp搭建_安装vsftpd2016-05-29回答首先在client上建立publickey和privatekey,需要使用ssh-keygen命令[root@localhost.ssh]#ssh-keygen–trsageneratingpublic/privatersakeypair.enterfileinwhichtosavethekey(/root/.ssh/id_rsa…

  • 静态代理与动态代理_java静态代理动态代理

    静态代理与动态代理_java静态代理动态代理讲解静态代理与动态代理的实现示例,静态代理与动态代理的区别

  • PHP进销存erp源码库存管理系统

    PHP进销存erp源码库存管理系统PHP进销存erp源码库存管理系统(2次开发另外收费)本系统开发PHP+MySQL采用CI2.x框架本系统运行环境php5.3+mysql5.5支持IIS、apache不支持nginx源码网站:www.phprr.com演示地址:http://www.phprr.com/show-55账号:admin密码:jxc888888…

发表回复

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

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