当前位置: 首页 > news >正文

六、分组背包

六、分组背包

  • 题记
  • 算法
  • 题目
  • 代码

题记

一个旅行者有一个最多能装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[k1][v],f[k1][vw[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件物品&#xff0c;它们的重量分别是W[1]&#xff0c;W[2]&#xff0c;…,W[n]&#xff0c;它们的价值分别为C[1],C[2],…,C[n]。这些物品被划分为若干组&#xff0c;每组中的物品互相冲突&#…...

LangChain入门:构建LLM驱动的应用程序的初学者指南

LangChain & DemoGPT 一、介绍 你有没有想过如何使用大型语言模型&#xff08;LLM&#xff09;构建强大的应用程序&#xff1f;或者&#xff0c;也许您正在寻找一种简化的方式来开发这些应用程序&#xff1f;那么你来对地方了&#xff01;本指南将向您介绍LangChain&#x…...

gitlab修改远程仓库地址

目录 背景&#xff1a; 解决&#xff1a; 1.删除本地仓库关联的远程地址&#xff0c;添加新的远程仓库地址 2.直接修改本地仓库关联的远程仓库地址 3.打开.git隐藏文件修改远程仓库地址 4.拉取代码报错(git host key verification failed) 背景&#xff1a; 公司搬家&#…...

VB+SQL自动点歌系统设计与实现

摘 要 随着社会的发展,人类的进步,21世纪人们的生活的水平有所提高,为了满足人们对生活的需要,丰富业余生活,就需要有一些娱乐的设施来弥补这些空缺,所以开发了自动点歌系统。 论文详细论述了系统总体设计思想、数据库设计以及功能模块设计等,给出了自动点歌系统一般流程…...

设计模式之适配器模式(Adapter)的C++实现

1、适配器模式的提出 在软件功能开发中&#xff0c;由于使用环境的改变&#xff0c;之前一些类的旧接口放在新环境的功能模块中不再适用。如何使旧接口能适用于新的环境&#xff1f;适配器可以解决此类问题。适配器模式&#xff1a;通过增加一个适配器类&#xff0c;在适配器接…...

C#系统锁屏事件例子 - 开源研究系列文章

今天有个网友问了个关于操作系统锁屏的问题。 我们知道&#xff0c;操作系统是基于消息和事件处理的&#xff0c;所以我们只要找到该操作系统锁屏和解屏的那个事件&#xff0c;然后在事件里进行处理即可。下面是例子介绍。 1、 项目目录&#xff1b; 下面是项目目录&#xff1a…...

R语言实现免疫浸润分析(2)

原始数据承接免疫浸润分析&#xff08;1&#xff09;&#xff0c;下面展示免疫浸润结果&#xff1a; #直接使用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设置成输出模式&#xff0c;并通过将GPIO的电平拉高拉低控制LED灯的例程。GPIO除了用作输出功能之外&#xff0c;还可以用作输入功能。最常用的就是检测按键的输入电平。 硬件设计 本章的硬件是基于正点原子的探索者…...

Jenkins-CICD-python/Java包升级与回退

Jenkins- CICD流水线 python/Java代码升级与回退 1、执行思路 1.1、代码升级 jenkins上点击 upgrade和 代码版本号 --${tag} jenkins 推送 代码 和 执行脚本 到目标服务器/opt目录下 执行命令 sh run.sh 代码名称 版本号 upgrade 版本号 来自jenkins的 构建参数中的 标签…...

模糊测试面面观 | 模糊测试工具知多少

自1988年威斯康星大学的Barton Miller首次提出模糊测试这一概念以来&#xff0c;模糊测试领域经历了持续长久发展。模糊测试作为一种软件测试方法&#xff0c;旨在通过向程序输入模糊、随机、异常的数据&#xff0c;探测和发现潜在的漏洞和错误。这种方法备受安全研究人员的青睐…...

esp8266+电压检测模块检测电池电压

该模块5v时输出1v&#xff0c;因esp8266 ADC引脚(A0)支持电压范围是0v-1v&#xff0c;所以该方案仅支持0-5v电压检测 接线&#xff1a; - 接 esp8266GND 可不接 S 接 ADC esp8266 为 A0 VCC 被检测直流电 GND 被检测直流电- #include <Wire.h>const int adcPin A0; // …...

MongoDB增删改查操作

数据库操作&#xff1a; 在MongoDB中&#xff0c;文档集合存在数据库中。 要选择使用的数据库&#xff0c;请在mongo shell程序中发出 use <db> 语句 // 查看有哪些数据库 show dbs;// 如果数据库不存在&#xff0c;则创建并切换到该数据库&#xff0c;存在则直接切换到…...

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. 微信小程序开发环境搭建

下载 微信的小程序开发需要使用到微信开发者工具&#xff0c;通过https://developers.weixin.qq.com/miniprogram/dev/devtools/stable.html可以下载 下载完成后 安装...

Redis五大基本数据类型及其使用场景

文章目录 **一 什么是NoSQL&#xff1f;****二 redis是什么&#xff1f;****三 redis五大基本类型**1 String&#xff08;字符串&#xff09;**应用场景** 2 List&#xff08;列表&#xff09;**应用场景** 3 Set&#xff08;集合&#xff09;4 sorted set&#xff08;有序集合…...

优于立方复杂度的 Rust 中矩阵乘法

优于立方复杂度的 Rust 中矩阵乘法 迈克克维特 跟随 发表于 更好的编程 6 分钟阅读 7月 <> 143 中途&#xff1a;三次矩阵乘法 一、说明 几年前&#xff0c;我在 C 年编写了 Strassen 矩阵乘法算法的实现&#xff0c;最近在 Rust 中重新实现了它&#xff0c;因为我继续…...

CentOS gcc介绍及快速升级

1.gcc介绍 GCC&#xff08;GNU Compiler Collection&#xff09;是一个开源的编译器套件&#xff0c;由 GNU(GNUs Not Unix!的递归缩写) 项目开发和维护。它是一个功能强大且广泛使用的编译器&#xff0c;支持多种编程语言&#xff0c;包括 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日报

&#x1f440;日报&周刊合集 | &#x1f3a1;生产力工具与行业应用大全 | &#x1f9e1; 点赞关注评论拜托啦&#xff01; &#x1f916; 一则AI工程师招募信息&#xff1a;新领域需要新技能 Vision Flow (目的涌现) 是一家基于 AGI 原生技术的创业公司&#xff0c;是全球探…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...