(AcWing)分组背包问题
有 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;
}
相关文章:
(AcWing)分组背包问题
有 N 组物品和一个容量是 V 的背包。 每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。 求解将哪些物品装入背包,可使物品总体积不超过背包容量&…...
JSP项目国际化词条统计
国际化字条匹配并导出为excel格式 需求 将jsp页面里的key值,就是<spring:message code"gsyezer_Single_crystal"/>里的gsyezer_Single_crystal。和对应的字条对应上,并以excel表格形式输出。 jsp页面key值示例 <label for"&…...
Java课题笔记~ MyBatis缓存
为了减少重复查询给数据库带来的压力,MyBatis提供了缓存机制,这种机制能够缓存查询的结果,避免重复的查询。 MyBatis提供了两种缓存方式: 一种为针对于SqlSession的缓存【默认开启】 另一种为针对于全局的缓存【手动开启】 一…...
数据结构--循环队列、链队
基础知识 //循环队列数据结构 typedef struct { QElemType data[MaxQSize];//数据域 int front,rear; //队头队尾指针 }SqQueue; //链队结点数据结构 typedef struct QNode { int data;//数据域 struct QNode* next;//指针域 }QNode, * QueuePtr; typedef struct { struct Q…...
hbuilderx主题色分享-github风格
效果 步骤 hbuilderx总共有三种主题,绿柔主题Default,酷黑主题Monokai,雅黑主题Atom One Dark,修改主题色是基于三种主题之一的,不能直接创建一个新主题,比如下方配置是基于Atom One Dark(对象名为[Atom One Dark]),则当前hbuild…...
【C++】类与对象(1)
文章目录 前言一、什么是类1.类的定义2.类的访问限定符3.类的作用域 二、类的实例化三、类对象的存储方式四、this指针总结 前言 C语言是面向过程的,关注的是过程,分析出求解问题的步骤,通过函数调用逐步解决问题。C是基于面向对象的&#x…...
Java课题笔记~ MyBatis核心配置
一、核心配置文件概览 MyBatis配置文件中有MyBatis框架的核心配置,负责对MyBatis进行全局管理。它包含许多控制MyBatis功能的重要元素。 <configuration><!--设置配置文件--><properties><property name"" value""/>…...
从0开始自学网络安全(黑客)
前言 黑客技能是一项非常复杂和专业的技能,需要广泛的计算机知识和网络安全知识。你可以参考下面一些学习步骤,系统自学网络安全。 在学习之前,要给自己定一个目标或者思考一下要达到一个什么样的水平,是学完找工作(…...
kotlin 编写一个简单的天气预报app(四)增加界面显示
编写界面来显示返回的数据 用户友好性:通过界面设计和用户体验优化,可以使天气信息更易读、易理解和易操作。有效的界面设计可以提高用户满意度并提供更好的交互体验。 增加城市名字的TextView <TextViewandroid:id"id/textViewCityName"…...
英语不好能学好Python吗?Python常用英文单词汇总
前言 嗨喽,大家好呀~这里是爱看美女的茜茜呐 有些小可爱对英语好不好对学习python有没有什么影响有着很深的疑惑。 其实python学习,主要靠多敲多练,主打一个熟能生巧 那今天我就给大家带来Python常用英文单词汇总, 新手期小可…...
Counting Stars 2023“钉耙编程”中国大学生算法设计超级联赛(5)hdu7335
Problem - 7335 题目大意:如果一个点连接着k个点,就称这k1个点构成k星图,现给出一个大小为n的图,问2星图的数量^3星图的数量^...^n星图的数量是多少 3<n<1e6;1<m<1e6 思路:因为边数总共不超过1e6&#…...
浅谈document.write()输出样式
浅谈document.write()输出样式 js中的最基本的命令之一:document.write(),用于简单的打印内容到页面上,可以逐字打印你需要的内容——document.write("content"),这里content就是需要输出的内容;…...
AIGC(Artificial Intelligence and Graph Computing)职业发展路径和前景如何?
目录 一、AIGC 基本概念二、AIGC 市场规模三、AIGC 未来发展前景四、AIGC 职业发展路径五、AIGC 技能要求六、AIGC 相关公司 AIGC(Artificial Intelligence and Graph Computing)是人工智能和图计算的结合,它是一种用于处理大规模复杂数据的计…...
MySql006——基本的SELECT查询语句
在《MySql003——结构化查询语言SQL基础知识》中,我们学习了有关SQL的基础知识,也知道SQL中查询语句SELECT使用最为频繁 接下来我们将学习一些基本的SELECT查询语句 一、SELECT语句的通用语法 在MySQL数据库中,使用SELECT语句可以查询数据…...
【啥都生】分类项目中的模型搭建代码解析
def build_model(cfg):if isinstance(cfg, list):modules [eval(cfg_.pop("type"))(**cfg_) for cfg_ in cfg]return Sequential(*modules)else:return eval(cfg.pop("type"))(**cfg)b站up啥都生维护的分类项目 这段代码的功能是完成模型搭建,…...
Ubuntu出现了内部错误
使用的Ubuntu版本是18.04,使用的时候弹出对话框说出现了内部错误,好奇是哪里出现了错误,查找了一下解决的办法,记录一下。 参考解决方案:ubantu出现了内部错误 一旦程序崩溃过一次,就会生成一个.crash文件…...
Stable Diffusion AI绘画初学者指南【概述、云端环境搭建】
概述、云端环境搭建 Stable Diffusion 是什么、能干啥? 是一种基于深度学习的图像处理技术,可以生成高质量的图像。它可以在不需要真实图像的情况下,通过文字描述来生成逼真的图像。 可以对图像进行修复、超分辨率转换,将低分辨…...
小程序动态隐藏分享按钮
// 禁用分享 wx.hideShareMenu({menus: [shareAppMessage, shareTimeline] })// 显示分享 wx.showShareMenu({withShareTicket: true,menus: [shareAppMessage, shareTimeline] })//私密消息 wx.updateShareMenu({isPrivateMessage: true, })...
语音合成是什么?如何进行语音合成TTS数据采集?
我们在上一篇讲到语音数据采集分为常见的两种语音数据采集类型,一个是语音识别数据(ASR),另一个是语音合成(TTS)。这一期中,我们将介绍语音合成技术是什么,如何采集语音合成数据和制…...
实用干货!一文读懂Salesforce中6种数据关系类型!
Salesforce中对象之间的数据关系可能是一个棘手的话题。对于创建自定义对象的业务场景,需要决定使用哪些关系类型来扩展Salesforce数据模型。 01 查找关系 查找关系(Lookup Relationships)是一种松散耦合(loosely coupled&…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
