acwing-9. 分组背包问题(分组背包)

acwing-9. 分组背包问题(分组背包)有 N 组物品和一个容量是 V 的背包。每组物品有若干个,同一组内的物品最多只能选一个。每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。接下来有 N 组数据:每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i

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

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

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

每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

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

输出最大价值。

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

接下来有 N 组数据:

每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;
输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100

输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例:
8

题解
for 物品
for 体积
for 决策

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

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

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

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

(0)


相关推荐

  • java Calendar日期相减问题

    java Calendar日期相减问题两个日期相减,必须是Date型变量使用其getTime()后相减,所以如果是从Calendar获得时间,则需:Calendardate1=Calendar.getInstance();Calendardate2=Calendar.getInstance();date1.getTime().getTime()-date2.getTime().getTime();结果为

  • get请求有长度限制吗_http请求最大长度

    get请求有长度限制吗_http请求最大长度错误提示:HTTPError404.15-NotFoundTherequestfilteringmoduleisconfiguredtodenyarequestwherethequerystringistoolong.原因:IE的get请求url默认是2k(各个浏览器或许不一样,但是get请求是有长度限制的)解决:…

  • ANT安装、环境变量配置及验证

    ANT安装、环境变量配置及验证一、安装ant到官方主页http://ant.apache.org下载新版(目前为Ant1.8.1)的ant,得到的是一个apache-ant-1.8.1-bin.zip的压缩包。将其解压到你的硬盘上,例如:C:\apache-ant-1.8.1。二、配置环境变量window中设置ant环境变量:ANT_HOME   C:/apache-ant-1.8.1path    

  • hackbar常用误区

    hackbar常用误区在web题目中,hackbar使用可以说是非常频繁,但不同hackbar使用上有略微区别.推荐使用googlechrome下的hackbar如果是firefox的话,hackbar有略微缺陷post的数据必须是键值对,不可以直接post数据比如说我想要利用inlcude($_GET)洞利用php://input的时候想要postphpinfo();结果点execute没有反应而googlechrome下的没有问题下面是安装这种非键值对也可以成功…

  • 用iptable防止ddos「建议收藏」

    用iptable防止ddos「建议收藏」DDoSdeflate是一款Linux/centos减轻/防止ddos攻击的一个小程序,相当于软件防火墙。注意,此程序仅仅能抵御较低流量的攻击,大流量攻击连用了上百台高档服务器做了负载均衡的新浪都扛不住,何况一个小小的普通服务器或vps。对此程序不要期望过高。这里仅仅介绍一下,对于一些简单的软件攻击可能还有点作用。CTOHOM制作的DDoSdeflate一键安装脚本:wge…

  • 久违的黑客手册[通俗易懂]

    久违的黑客手册[通俗易懂]今天终于看到那件书店上摆上了《黑客手册》高兴的不得了抓起一本就跑去付帐排队的时候拿起封面看了看 晕3月份的了 55  。。。1,2月的没的买了 真不爽偏偏老板就不进1,2月的偏偏这里就这一间店有这书卖当我把钱递给老板的时候老板突然问我一句话让我苦笑不得他说看你每次都买这书你是黑客还是红客啊?……我只好开玩笑的说我红黑同杀^_^….

发表回复

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

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