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

多重背包问题 ⅠⅡ Ⅲ

有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

输入
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

输出
输出一个整数,表示最大价值。

Input
4 5
1 2 3
2 4 1
3 4 3
4 5 2

Output
10

根据不同的数据范围,有不同的选择

Ⅰ.  数据范围   0<N,V≤100  0<vi,wi,si≤100      

直接写

//代码一
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=510,M=6010;
int n,m;
int v,w,s;
int f[N][M];
void solve()
{cin>>n>>m;for (int i=1;i<=n;i++){cin>>v>>w>>s;for (int j=1;j<=m;j++)for (int k=0;k<=s&&k*v<=j;k++)f[i][j]=max(f[i][j],f[i-1][j-k*v]+k*w);}cout<<f[n][m];
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}//代码二:降一维
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=510,M=6010;
int n,m;
int v,w,s;
int f[M];
void solve()
{cin>>n>>m;for (int i=1;i<=n;i++){cin>>v>>w>>s;for (int j=m;j>=v;j--)for (int k=0;k<=s&&k*v<=j;k++)f[j]=max(f[j],f[j-k*v]+k*w);}cout<<f[m];
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}

Ⅱ.  数据范围   0<N≤1000,0<V≤2000,0<vi,wi,si≤2000      

通过二进制将每种物品按照个数的不同重新打包,再按01背包的方式选择

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=1e6+10;
int n,m;
int f[N],v[N],w[N];
int cnt;
void solve()
{cin>>n>>m;for (int i=1;i<=n;i++){int a,b,s;cin>>a>>b>>s;int k=1;while (k<=s){cnt++;v[cnt]=k*a;w[cnt]=k*b;s -=k;k *=2;}if (s>0){cnt++;v[cnt]=s*a;w[cnt]=s*b;}}for (int i=1;i<=cnt;i++)for (int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[m];
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}

Ⅲ.  数据范围   0<N≤1000,0<V≤20000,0<vi,wi,si≤20000

通过单调队列来更新状态

//代码一
#include <bits/stdc++.h>
using namespace std;
//#define int long long         //不开就不开吧
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=1010,M=2e4+10;
int n,m;
int f[N][M],q[M];
void solve()
{cin>>n>>m;for (int i=1;i<=n;i++){int v,w,s;cin>>v>>w>>s;for (int j=0;j<v;j++){int hh=0,tt=-1;for (int k=j;k<=m;k +=v){if (hh<=tt&&k-q[hh]>s*v) hh++;      //判断队头是否滑出窗口,队列中的v不能超过上限s个while (hh<=tt&&f[i-1][q[tt]]-(q[tt]-j)/v*w<=f[i-1][k]-(k-j)/v*w) tt--;q[++tt]=k;f[i][k]=f[i-1][q[hh]]+(k-q[hh])/v*w;}}}cout<<f[n][m];
}
int main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}//代码二 降一维
#include <bits/stdc++.h>
using namespace std;
//#define int long long         //不开就不开吧
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e4+10;
int n,m;
int f[N],g[N],q[N];
void solve()
{cin>>n>>m;for (int i=1;i<=n;i++){int v,w,s;cin>>v>>w>>s;memcpy(g,f,sizeof f);       //滚动数组,备份上一次的状态for (int j=0;j<v;j++){int hh=0,tt=-1;for (int k=j;k<=m;k +=v){if (hh<=tt&&k-q[hh]>s*v) hh++;      //判断队头是否滑出窗口,队列中的v不能超过上限s个while (hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w) tt--;q[++tt]=k;f[k]=g[q[hh]]+(k-q[hh])/v*w;}}}cout<<f[m];
}
int main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}

相关文章:

多重背包问题 ⅠⅡ Ⅲ

有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件&#xff0c;每件体积是 vi&#xff0c;价值是 wi。 求解将哪些物品装入背包&#xff0c;可使物品体积总和不超过背包容量&#xff0c;且价值总和最大。 输出最大价值。 输入 第一行两个整数&#xff0c;N&#xf…...

挑战杯 python的搜索引擎系统设计与实现

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; python的搜索引擎系统设计与实现 &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度系数&#xff1a;3分工作量&#xff1a;5分创新点&#xff1a;3分 该项目较为新颖&#xff…...

【LeetCode: 103. 二叉树的锯齿形层序遍历 + BFS】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…...

C#学习(十三)——多线程与异步

一、什么是线程 程序执行的最小单元 一次页面的渲染、一次点击事件的触发、一次数据库的访问、一次登录操作都可以看作是一个一个的进程 在一个进程中同时启用多个线程并行操作&#xff0c;就叫做多线程 由CPU来自动处理 线程有运行、阻塞、就绪三态 代码示例&#xff1a; cl…...

MySQL 数据库安装教程详解(linux系统和windows系统)

MySQL 数据库是一种广泛使用的开源关系数据库管理系统。在 Linux 和 Windows 系统上安装 MySQL 数据库的步骤略有不同。以下是详细的安装教程。 Linux 系统安装教程 1. **安装前提**&#xff1a;确保你的 Linux 系统已经安装了 wget、unzip、tar 等必要的工具。 2. **下…...

从汇编分析C语言可变参数的原理,并实现一个简单的sprintf函数

C语言可变参数 使用printf等函数的时候函数原型是printf(const char* fmt, ...), 这一类参数的个数不限的函数是可变参数 使用 使用一个头文件stdarg.h, 主要使用以下的宏 typedef char * va_list;// 把 n 圆整到 sizeof(int) 的倍数 #define _INTSIZEOF(n) ( (sizeo…...

Word docx文件重命名为zip文件,解压后直接查看和编辑

一个不知道算不算冷的知识[doge]&#xff1a; docx格式的文件本质上是一个ZIP文件 当把一个.docx文件重命名为.zip文件并解压后&#xff0c;你会发现里面包含了一些XML文件和媒体文件&#xff0c;它们共同构成了Word文档的内容和格式。 例如&#xff0c;word/document.xml文件…...

SpringBoot中公共字段的自动填充

目录 1 前言 2 使用方法 2.1 自定义枚举类 2.2 自定义注解AutoFill 2.3 自定义切面类并设定切入点 2.4 切面类中设置前置通知&#xff0c;对公共字段赋值 2.5 在方法上添加自定义注解 3 最后 1 前言 在我们的项目中&#xff0c;项目表可能会有一些公共的字段需要我们的…...

【天衍系列 03】深入理解Flink的Watermark:实时流处理的时间概念与乱序处理

文章目录 01 基本概念02 工作原理03 优势与劣势04 核心组件05 Watermark 生成器 使用06 应用场景07 注意事项08 案例分析8.1 窗口统计数据不准8.2 水印是如何解决延迟与乱序问题&#xff1f;8.3 详细分析 09 项目实战demo9.1 pom依赖9.2 log4j2.properties配置9.3 Watermark水印…...

day07.C++类与对象

一.类与对象的思想 1.1面向对象的特点 封装、继承、多态 1.2类的概念 创建对象的过程也叫类的实例化。每个对象都是类的一个具体实例&#xff08;Instance&#xff09;&#xff0c;拥有类的成员变量和成员函数。由{ }包围&#xff0c;由&#xff1b;结束。 class name{ //类的…...

String讲解

文章目录 String类的重要性常用的方法常用的构造方法String类的比较字符串的查找转化数字转化为字符串字符串转数字 字符串替换字符串的不可变性 字符串拆分字符串截取字符串修改 StringBuilder和StringBuffer String类的重要性 在c/c的学习中我们接触到了字符串&#xff0c;但…...

人群异常聚集监测系统-聚众行为检测与识别算法---豌豆云

聚众识别系统对指定区域进行实时监测&#xff0c;当监测到人群大量聚集、达到设置上限时&#xff0c;立即告警及时疏散。 旅游业作为国民经济战略性支柱产业&#xff0c;随着客流量不断增加&#xff0c;旅游景区和一些旅游城市的管理和服务面临着前所未有的挑战&#xff1a; …...

多模态基础---BERT

1. BERT简介 BERT用于将一个输入的句子转换为word_embedding&#xff0c;本质上是多个Transformer的Encoder堆叠在一起。 其中单个Transformer Encoder结构如下&#xff1a; BERT-Base采用了12个Transformer Encoder。 BERT-large采用了24个Transformer Encoder。 2. BERT的…...

图表示学习 Graph Representation Learning chapter2 背景知识和传统方法

图表示学习 Graph Representation Learning chapter2 背景知识和传统方法 2.1 图统计和核方法2.1.1 节点层次的统计和特征节点的度 节点中心度聚类系数Closed Triangles, Ego Graphs, and Motifs 图层次的特征和图的核节点袋Weisfieler–Lehman核Graphlets和基于路径的方法 邻域…...

OpenMVG(计算两个球形图像之间的相对姿态、细化重建效果)

目录 1 Bundle Adjustment(细化重建效果) 2 计算两个球形图像之间的相对姿态 1 Bundle Adjustment(细化重建效果) 数...

【QT+QGIS跨平台编译】之三十四:【Pixman+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、Pixman介绍二、文件下载三、文件分析四、pro文件五、编译实践一、Pixman介绍 Pixman是一款开源的软件库,提供了高质量的像素级图形处理功能。它主要用于在图形渲染、合成和转换方面进行优化,可以帮助开发人员在应用程序中实现高效的图形处理。 Pixman的主要特…...

2.17学习总结

tarjan 【模板】缩点https://www.luogu.com.cn/problem/P3387 题目描述 给定一个 &#xfffd;n 个点 &#xfffd;m 条边有向图&#xff0c;每个点有一个权值&#xff0c;求一条路径&#xff0c;使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者…...

Unity类银河恶魔城学习记录7-7 P73 Setting sword type源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili Sword_Skill_Controller.cs using System.Collections; using System.Col…...

安卓版本与鸿蒙不再兼容,鸿蒙开发工程师招疯抢

最近&#xff0c;互联网大厂纷纷开始急招华为鸿蒙开发工程师。这是一个新的信号。在Android和iOS长期霸占市场的今天&#xff0c;鸿蒙的崛起无疑为整个行业带来了巨大的震动。 2023年11月10日&#xff0c;网易更新了高级/资深Android开发工程师岗位&#xff0c;职位要求参与云音…...

《白话C++》第9章 泛型,Page842~844 9.4.2 AutoPtr

源起&#xff1a; C编程中&#xff0c;最容易出的问题之一&#xff0c;就是内存泄露&#xff0c;而new一个对象&#xff0c;却忘了delete它&#xff0c;则是造成内存泄露的主要原因之一 例子一&#xff1a; void foo() {XXXObject* xo new XXXObject;if(!xo->DoSomethin…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...