六、分组背包
六、分组背包
- 题记
- 算法
- 题目
- 代码
题记
一个旅行者有一个最多能装V公斤的背包和有N件物品,它们的重量分别是W[1],W[2],…,W[n],它们的价值分别为C[1],C[2],…,C[n]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
算法
这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值,则有 f [ k ] [ v ] = m a x f [ k − 1 ] [ v ] , f [ k − 1 ] [ v − w [ i ] ] + c [ i ] (物品 i 属于第 k 组) f[k][v]=max{f[k-1][v],f[k-1][v-w[i]]+c[i]}(物品i属于第k组) f[k][v]=maxf[k−1][v],f[k−1][v−w[i]]+c[i](物品i属于第k组)
使用一维数组的伪代码如下:
for 所有的组 kfor v=V..0for 所有的 i 属于组 kf[v]=max(f[v],f[v-w[i]]+c[i])
题目
1272:【例9.16】分组背包
【题目描述】
一个旅行者有一个最多能装V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,…,Wn,它们的价值分别为C1,C2,…,Cn。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
【输入】
第一行:三个整数,V(背包容量,V≤200),N(物品数量,N≤30)和T(最大组号,T≤10);
第2…N+1行:每行三个整数Wi,Ci,P,表示每个物品的重量,价值,所属组号。
【输出】
仅一行,一个数,表示最大总价值。
【输入样例】
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3
【输出样例】
20
代码
#include<bits/stdc++.h>
using namespace std;
int n,v,t;
int w[310],c[310],a[310][310],f[310];
//a[p][0]数组记录每组有多少物品
int main() {cin>>v>>n>>t;for(int i=1; i<=n; i++) {int p;cin>>w[i]>>c[i]>>p;a[p][++a[p][0]]=i; }for(int p=1; p<=t; p++)for(int j=v; j>=0; j--)for(int i=1; i<=a[p][0]; i++)//循环每一组数据中的物品 if(j>=w[a[p][i]])//保证数组不会越界 f[j]=max(f[j],f[j-w[a[p][i]]]+c[a[p][i]]);//计算最大价值 cout<<f[v];//输出在v公斤时的最大价值 return 0;
}
相关文章:
六、分组背包
六、分组背包 题记算法题目代码 题记 一个旅行者有一个最多能装V公斤的背包和有N件物品,它们的重量分别是W[1],W[2],…,W[n],它们的价值分别为C[1],C[2],…,C[n]。这些物品被划分为若干组,每组中的物品互相冲突&#…...
LangChain入门:构建LLM驱动的应用程序的初学者指南
LangChain & DemoGPT 一、介绍 你有没有想过如何使用大型语言模型(LLM)构建强大的应用程序?或者,也许您正在寻找一种简化的方式来开发这些应用程序?那么你来对地方了!本指南将向您介绍LangChain&#x…...
gitlab修改远程仓库地址
目录 背景: 解决: 1.删除本地仓库关联的远程地址,添加新的远程仓库地址 2.直接修改本地仓库关联的远程仓库地址 3.打开.git隐藏文件修改远程仓库地址 4.拉取代码报错(git host key verification failed) 背景: 公司搬家&#…...
VB+SQL自动点歌系统设计与实现
摘 要 随着社会的发展,人类的进步,21世纪人们的生活的水平有所提高,为了满足人们对生活的需要,丰富业余生活,就需要有一些娱乐的设施来弥补这些空缺,所以开发了自动点歌系统。 论文详细论述了系统总体设计思想、数据库设计以及功能模块设计等,给出了自动点歌系统一般流程…...
设计模式之适配器模式(Adapter)的C++实现
1、适配器模式的提出 在软件功能开发中,由于使用环境的改变,之前一些类的旧接口放在新环境的功能模块中不再适用。如何使旧接口能适用于新的环境?适配器可以解决此类问题。适配器模式:通过增加一个适配器类,在适配器接…...
C#系统锁屏事件例子 - 开源研究系列文章
今天有个网友问了个关于操作系统锁屏的问题。 我们知道,操作系统是基于消息和事件处理的,所以我们只要找到该操作系统锁屏和解屏的那个事件,然后在事件里进行处理即可。下面是例子介绍。 1、 项目目录; 下面是项目目录:…...
R语言实现免疫浸润分析(2)
原始数据承接免疫浸润分析(1),下面展示免疫浸润结果: #直接使用IOBR包内的cell_bar_plot pic<-cell_bar_plot(input quantiseq_immo_de[1:20,], title "quanTiseq Cell Fraction") #使用ggplot2 library(ggplot2)…...
系统架构设计师-信息安全技术(2)
目录 一、安全架构概述 1、信息安全所面临的威胁 二、安全模型 1、安全模型的分类 2、BLP模型 3、Biba 模型 4、Chinese Wall模型 三、信息安全整体架构设计 1、WPDRRC模型 2、各模型的安全防范功能 四、网络安全体系架构设计 1、开放系统互联安全体系结构 2、安全服务与安…...
STM32F4X-GPIO输入功能使用
STM32F4 GPIO输入模式配置 上一节讲GPIO的时候说到了将GPIO设置成输出模式,并通过将GPIO的电平拉高拉低控制LED灯的例程。GPIO除了用作输出功能之外,还可以用作输入功能。最常用的就是检测按键的输入电平。 硬件设计 本章的硬件是基于正点原子的探索者…...
Jenkins-CICD-python/Java包升级与回退
Jenkins- CICD流水线 python/Java代码升级与回退 1、执行思路 1.1、代码升级 jenkins上点击 upgrade和 代码版本号 --${tag} jenkins 推送 代码 和 执行脚本 到目标服务器/opt目录下 执行命令 sh run.sh 代码名称 版本号 upgrade 版本号 来自jenkins的 构建参数中的 标签…...
模糊测试面面观 | 模糊测试工具知多少
自1988年威斯康星大学的Barton Miller首次提出模糊测试这一概念以来,模糊测试领域经历了持续长久发展。模糊测试作为一种软件测试方法,旨在通过向程序输入模糊、随机、异常的数据,探测和发现潜在的漏洞和错误。这种方法备受安全研究人员的青睐…...
esp8266+电压检测模块检测电池电压
该模块5v时输出1v,因esp8266 ADC引脚(A0)支持电压范围是0v-1v,所以该方案仅支持0-5v电压检测 接线: - 接 esp8266GND 可不接 S 接 ADC esp8266 为 A0 VCC 被检测直流电 GND 被检测直流电- #include <Wire.h>const int adcPin A0; // …...
MongoDB增删改查操作
数据库操作: 在MongoDB中,文档集合存在数据库中。 要选择使用的数据库,请在mongo shell程序中发出 use <db> 语句 // 查看有哪些数据库 show dbs;// 如果数据库不存在,则创建并切换到该数据库,存在则直接切换到…...
Python | Package | Python的三种包安装方式(pip/whl/tar.gz)
文章目录 PIP 安装与卸载Source 安装与卸载Whell 安装与卸载 PIP 安装与卸载 pip install xxx pip install xxxversion_numberpip install captcha pip install captcha0.4# XXX/anaconda3/envs/py373/lib/python3.7/site-packages pip uninstall captchaSource 安装与卸载 p…...
1. 微信小程序开发环境搭建
下载 微信的小程序开发需要使用到微信开发者工具,通过https://developers.weixin.qq.com/miniprogram/dev/devtools/stable.html可以下载 下载完成后 安装...
Redis五大基本数据类型及其使用场景
文章目录 **一 什么是NoSQL?****二 redis是什么?****三 redis五大基本类型**1 String(字符串)**应用场景** 2 List(列表)**应用场景** 3 Set(集合)4 sorted set(有序集合…...
优于立方复杂度的 Rust 中矩阵乘法
优于立方复杂度的 Rust 中矩阵乘法 迈克克维特 跟随 发表于 更好的编程 6 分钟阅读 7月 <> 143 中途:三次矩阵乘法 一、说明 几年前,我在 C 年编写了 Strassen 矩阵乘法算法的实现,最近在 Rust 中重新实现了它,因为我继续…...
CentOS gcc介绍及快速升级
1.gcc介绍 GCC(GNU Compiler Collection)是一个开源的编译器套件,由 GNU(GNUs Not Unix!的递归缩写) 项目开发和维护。它是一个功能强大且广泛使用的编译器,支持多种编程语言,包括 C、C、Objective-C、Fortran、Ada 和…...
IO多路复用中select的TCP服务器模型和poll服务模型
select的TCP服务器模型 服务器端 #include <head.h> #include <sys/types.h> #include <sys/socket.h> #include <arpa/inet.h> #include <unistd.h> #include <sys/select.h> #include <sys/time.h>#define PORT 6666 //1024~4…...
AI工程师招募;60+开发者AI工具清单;如何用AI工具读懂插件源码;开发者出海解读;斯坦福LLM课程 | ShowMeAI日报
👀日报&周刊合集 | 🎡生产力工具与行业应用大全 | 🧡 点赞关注评论拜托啦! 🤖 一则AI工程师招募信息:新领域需要新技能 Vision Flow (目的涌现) 是一家基于 AGI 原生技术的创业公司,是全球探…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
