(AcWing)分组背包问题

news/2024/4/15 14:58:35

有 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
#include <iostream>
#include <algorithm>
using namespace std;const int N = 110; // 定义常量N表示物品种类数和最大值int v[N][N], w[N][N], s[N]; // 分别存储每个物品的体积、价值和数量
int f[N]; // 存储背包容量为j时的最大总价值int n, m; // 物品种类数和背包容量int main()
{cin >> n >> m; // 输入物品种类数n和背包容量mfor (int i = 1; i <= n; i++){cin >> s[i]; // 输入第i种物品的数量s[i]for (int j = 1; j <= s[i]; j++)cin >> v[i][j] >> w[i][j]; // 输入第i种物品的体积v[i][j]和价值w[i][j]}for (int i = 1; i <= n; i++) // 遍历每个物品种类{for (int j = m; j >= 0; j--) // 遍历背包容量从m到0{for (int k = 1; k <= s[i]; k++) // 遍历第i种物品的所有数量{if (j >= v[i][k]) // 如果当前背包容量可以放下第i种物品的第k个数量f[j] = max(f[j], f[j - v[i][k]] + w[i][k]); // 更新背包容量为j时的最大总价值}}}cout << f[m] << endl; // 输出背包容量为m时的最大总价值return 0;
}

 


http://www.ppmy.cn/news/1001422.html

相关文章

基于VUE3+Layui从头搭建通用后台管理系统(前端篇)七:工作台界面实现

一、本章内容 本章实现工作台界面相关内容,包括echart框架引入,mock框架引入等,实现工作台界面框架搭建,数据加载。 1. 详细课程地址: 待发布 2. 源码下载地址: 待发布 二、界面预览 三、开发视频 基于VUE3+Layui从头搭建通用后台管理系统合集-工作台界面布局实现 五、…

机器学习实战13-超导体材料的临界温度预测与分析(决策树回归,梯度提升回归,随机森林回归和Bagging回归)

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下机器学习实战13-超导体材料的临界温度预测与分析(决策树回归,梯度提升回归,随机森林回归和Bagging回归)&#xff0c;这几天引爆网络的科技大新闻就是韩国科研团队宣称发现了室温超导材料-LK-99&#xff0c;这种材料…

Flutter Flar动画实战

在Flare动面出现之前,Flare动画大体可以分为使用AnimationController控制的基础动画以及使用Hero的转场动画,如果遇到一些复杂的场景,使用这些动画方案实现起来还是有难度的。不过,随着Flutter开始支持Flare矢量动面,Flutter的动画开发也变得越来越简单。事实上,Flare动画…

远程仓库的操作

一、远程仓库的操作命令 git remote # 查看当前项目关联的远程库 我事先关联了一个GitHub的远程仓库&#xff0c;关于如何关联远程仓库&#xff0c;可以看这篇文章远程仓库GitHub和Gitee_林涧泣的博客-CSDN博客 git remote add [仓库服务器名] [远程仓库地址] # 关联远程仓库…

【Vue】父子组件值及方法传递使用

父子组件值、方法引用 1、值 1.1 父组件获取子组件值 父组件 <template><div><button click"getChildValue">click</button><child ref"child"></child></div> </template><script> import Child…

1-搭建一个最简单的验证平台UVM,已用Questasim实现波形!

UVM-搭建一个最简单的验证平台&#xff0c;已用Questasim实现波形 1&#xff0c;背景知识2&#xff0c;".sv"文件搭建的UVM验证平台&#xff0c;包括代码块分享3&#xff0c;Questasim仿真输出&#xff08;1&#xff09;compile all&#xff0c;成功&#xff01;&…

为了规避风险,如何给大模型打水印?

大型语言模型&#xff0c;如最近开发的ChatGPT&#xff0c;可以撰写文件、创建可执行代码和回答问题&#xff0c;通常具有人类般的能力。 随着这些大模型的应用越来越普遍&#xff0c;越来越大的风险也显现了出来&#xff0c;它们可能被用于恶意目的。这些恶意目的包括&#xf…

php运算符的短路特性

php运算符的短路特性 1、逻辑运算符&#xff1a;逻辑与&#xff08;&&)和逻辑或&#xff08;||&#xff09;&#xff0c;存在着短路特性 PHP中有以下两个运算符具有短路的特性&#xff0c;他们是逻辑运算符的逻辑与&#xff08;&&)和逻辑或&#xff08;||&am…

C++ MQTT客户端

下面是一个简单的ROS节点的C MQTT客户端的示例&#xff0c;包括.h和.cpp文件。 很抱歉&#xff0c;我之前提供的代码中似乎有一些错误。下面是更新后的代码&#xff0c;修复了mqtt命名空间中disconnect_response的问题&#xff1a; mqtt_client.h&#xff1a; #ifndef MQTT_…

VR虚拟仿真技术在道路桥梁中有哪些具体应用?

虚拟现实(VR)是一种新兴的技术&#xff0c;可以为桥梁工程提供许多应用场景。以下是一些可能的应用场景&#xff1a; 1.桥梁设计和模拟 VR元宇宙可以用于桥梁的设计和模拟。工程师可以使用VR技术来创建桥梁的三维模型&#xff0c;并对其进行测试和优化。这可以帮助工程师更好地…

排查管家婆财务试算不平衡

总账的财务期初试算不平衡&#xff0c;就会导致不能成功开账。当分销A\V系列总账版本软件中出现试算不平衡的情况&#xff0c;应该如何排查&#xff1f;请按照下面的排查步骤操作吧。 PART.01 期初建账-账务期初&#xff0c;币种选择【综合本位币】&#xff0c;点下面的【试算…

微信小程序使用editor富文本编辑器 以及回显 全屏弹窗的模式

<!--富文本接收的位置--><view class"white-box"><view class"title"><view class"yellow-fence"></view><view class"v1">教研记录</view></view><view class"add-btn"…

测试工程师与研发工程师之间的差别

目录 为什么要讨论二者的差别? 测试工程师的分类 测试工程师与研发工程师之间的差别

Linux C 获取主机网卡名及 IP 的几种方法

在进行 Linux 网络编程时&#xff0c;经常会需要获取本机 IP 地址&#xff0c;除了常规的读取配置文件外&#xff0c;本文罗列几种个人所知的编程常用方法&#xff0c;仅供参考&#xff0c;如有错误请指出。 方法一&#xff1a;使用 ioctl() 获取本地 IP 地址 Linux 下可以使用…

【Spring Boot】请求参数传json数组,后端采用(pojo)新增案例(103)

请求参数传json数组&#xff0c;后端采用&#xff08;pojo&#xff09;接收的前提条件&#xff1a; 1.pom.xml文件加入坐标依赖&#xff1a;jackson-databind 2.Spring Boot 的启动类加注解&#xff1a;EnableWebMvc 3.Spring Boot 的Controller接受参数采用&#xff1a;Reque…

django使用ztree实现树状结构效果,子节点实现动态加载(l懒加载)

一、实现的效果 由于最近项目中需要实现树状结构的效果,考虑到ztree这个组件大家用的比较多,因此打算在django项目中集成ztree来实现树状的效果。最终实现的示例效果如下: 点击父节点,如果有子节点,则从后台动态请求数据,然后显示出子节点的数据。 二、实现思路 …

JVM面试突击班2

JVM面试突击班2 对象被判定为不可达对象之后就“死”了吗 对象的生命周期 创建阶段 &#xff08;1&#xff09;为对象分配存储空间 &#xff08;2&#xff09;开始构造对象 &#xff08;3&#xff09;从超类到子类对static成员进行初始化 &#xff08;4&#xff09;超类成…

SAS-数据集SQL垂直(纵向)合并

一、SQL垂直合并的基本语法 一个selectt对应一个表&#xff0c;select之间用set-operator连接&#xff0c;set-operator包括&#xff1a;except&#xff08;期望&#xff09;、intersect&#xff08;相交&#xff09;、union&#xff08;合并&#xff09;&#xff0c;outer un…

Spring mvc:SpringServletContainerInitializer

SpringServletContainerInitializer实现了Servlet3.0规范中定义的ServletContainerInitializer&#xff1a; public interface ServletContainerInitializer {void onStartup(Set<Class<?>> c, ServletContext ctx) throws ServletException; }SpringServletCont…

2023河南萌新联赛第(四)场 L.7是大奖?(数位DP基础)

文章目录 题目大意题解参考代码总结 题目大意 ( 1 ≤ l , r ≤ 1 0 18 ) (1\leq l,r\leq 10^{18}) (1≤l,r≤1018) 题解 由题目可得 ①&#xff1a;统计数字出现次数&#xff1b; ②&#xff1a;直接暴力计算无法得出&#xff1b; ③&#xff1a;输入给定区间。 满足使用数位…
最新文章