当前位置: 首页 > 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…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...