【动态规划】多重背包问题,分组背包问题
Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。
🌈个人主页:主页链接
🌈算法专栏:专栏链接
我会一直往里填充内容哒!
🌈LeetCode专栏:专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出
🌈代码仓库:Gitee链接
🌈点击关注=收获更多优质内容🌈
目录
题目:多重背包问题
题解:
代码实现:
优化:
代码实现:
题目:分组背包问题
题解:
代码实现:
完结撒花:
题目:多重背包问题
题解:
与完全背包问题不同的是,每种东西都是有限件,前两种状态就不再过多赘述,有疑问的uu们可以去看看这篇文章完全背包,第三种状态我们直接枚举即可:当能拿下k个物品时,与不拿k件物品去最大值。
代码实现:
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1100;
int v[N],s[N],w[N],f[N][N];int main()
{int n=0,V=0;cin>>n>>V;for(int i=1;i<=n;i++){cin>>v[i]>>w[i]>>s[i];}for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){for(int k=0;k*v[i]<=j&&k<=s[i];k++)f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);}}cout<<f[n][V];
}
优化:
这种做法虽然简单易懂,但时间复杂度为n^3,很容易就TLE了,所以我们必须优化一下。
这里有利用了一下快速幂(背增)的思想,不知道的uu们听我细说:
任何一个正整数都可以由二进制来表示(废话,那么我们要取得价值是不是也可以由二进制表示呢?
例如 我们有 1 2 4价值得东西,那我们就可以由这三个东西凑出0~7之间任何一个数
(由3个物品的表示凑出了7个情况),效率就高了
假设我们要凑0~9的任何一个数呢,那么1 2 4就无法表示了,我们可以给这区间加上一个2,是不是就可以表示0~9之间的任何一个情况了呢。
换到这题来看,数量为s的物品可以拆分为log s 个东西,就可以枚举出s个物品的情况,对应的价值乘上倍数k即可满足上面所说情况,所以对应的问题就变成了01背包问题
代码实现:
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110000000;
int v[N],s[N],w[N],f[N][N];int solution2()
{int n=0,V=0;cin>>n>>V;int cnt=0;int k=1;for(int i=1;i<=n;i++){int a=0,b=0,s=0;cin>>a>>b>>s;int k=1;while(k<=s){v[++cnt]=a*k;w[cnt]=b*k; s-=k;k*=2;}if(s>0){v[++cnt]=s*a;w[cnt]=s*b;}}n=cnt;for(int i=1;i<=n;i++){for(int j=V;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);}cout<<f[V];
}
题目:分组背包问题
题解:
这题与完全背包问题也十分的相似,就是将一件物品无限拿,变成了一组物品挑一个。
代码实现:
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int v[N][N],w[N][N],s[N],f[N];
int main()
{int n=0,m=0;cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=0;j<s[i];j++){cin>>v[i][j];cin>>w[i][j];}}for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){for(int k=0;k<s[i];k++){if(j>=v[i][k])f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}}}cout<<f[m];
}
完结撒花:
🌈本篇博客的内容【动态规划:多重背包问题,分组背包问题】已经结束。
🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。
🌈诸君,山顶见!
相关文章:
【动态规划】多重背包问题,分组背包问题
Halo,这里是Ppeua。平时主要更新C语言,C,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接 我会一直往里填充内容哒! &…...
JAVA面向对象特征之——封装
4.封装 private关键字 是一个权限修饰符 可以修饰成员(成员变量和成员方法) 作用是保护成员不被别的类使用,被private修饰的成员只在本类中才能访问 针对private修饰的成员变量,如果需要被其他类使用,提供相应的操作 提供 “get变量名()…...
【数据结构】二叉树相关OJ题
文章目录一、单值二叉树二、检查两颗树是否相同三、判断一棵树是否为另一颗树的子树四、对称二叉树五、二叉树的前序遍历六、二叉树中序遍历七、二叉树的后序遍历八、二叉树的构建及遍历一、单值二叉树 单值二叉树 题目描述 如果二叉树每个节点都具有相同的值,那…...
Windows安装Hadoop
当初搭建Hadoop、Hive、HBase、Flink等这些没有截图写文,今为分享特重装。下载Hadoop下载地址:https://mirrors.tuna.tsinghua.edu.cn/apache/hadoop/以管理员身份运行cmd切换到所在目录执行start winrar x -y hadoop-3.3.4.tar.gz,解压。配置…...
ICG-Hydrazide,吲哚菁绿-酰肼,ICG-HZ结构式,溶于二氯甲烷等部分有机溶剂,
ICG-Hydrazide,吲哚菁绿-酰肼 中文名称:吲哚菁绿-酰肼 英文名称:ICG-Hydrazide 英文别名:ICG-HZ 性状:粉末或固体 溶剂:溶于二氯甲烷等部分有机溶剂 稳定性:-20℃密封保存、置阴凉干燥处、防潮 分子…...
【论文阅读】浏览器扩展危害-Helping or Hindering? How Browser Extensions Undermine Security
本文来源于ACM CCS 2022; https://dl.acm.org/doi/10.1145/3548606.3560685 摘要 “浏览器扩展”是轻量级的浏览器附加组件,使用各个浏览器特定的功能丰富的JavaScript api,为用户提供了额外的Web客户端功能,如改进网站外观和与…...
线性和非线性最小二乘问题的常见解法总结
线性和非线性最小二乘问题的各种解法 先看这篇博客,非常好:线性和非线性最小二乘问题的各种解法 1. 线性最小二乘问题有最优解 但是面对大型稀疏矩阵的时候使用迭代法效率更好。 迭代法 有Jacobi迭代法、 Seidel迭代法及Sor法 【数值分析】Jacobi、Se…...
数据库知识点
数据库是指按照一定规则存储、组织和管理数据的系统。在现代化的信息化社会中,数据库已经成为了各种应用系统中不可或缺的一部分。因此,对于数据库的知识掌握不仅是计算机专业人员必备的技能,也是各个行业从业者必须具备的基本素质之一。 数…...
Maven打包构建Docker镜像并推送到仓库
Maven打包构建Docker镜像并推送到仓库 文章目录Maven打包构建Docker镜像并推送到仓库一,服务器Docker配置二,本地项目maven配置2.1 pom.xml2.2 dockerfile2.3 验证2.4 统一dockerfile对于开发完成的服务要发布至服务器Docker时,我刚学习了解D…...
TypeScript 基础学习之泛型和 extends 关键字
越来越多的团队开始使用 TS 写工程项目, TS 的优缺点也不在此赘述,相信大家都听的很多了。平时对 TS 说了解,仔细思考了解的也不深,借机重新看了 TS 文档,边学习边分享,提升对 TS 的认知的同时,…...
《数据分析-JiMuReport04》JiMuReport报表设计入门介绍-页面优化
报表设计 2 页面优化 如上图所示的报表,仅仅是展示数据,不过这样看起来似乎太草率了,所以再优化一下吧 保存报表后,在积木报表中就可以看到对应的报表文件 此时我们如果还需要编辑报表,就点击这个报表即可 2.1 居中…...
带头双向循环链表及链表总结
1、链表种类大全 1、链表严格来说可能用2*2*28种结构,从是否带头,是否循环,是否双向三个角度区分。 2、无头单向循环链表一般不会在实际运用中直接存储数据,而会作为某些更复杂结构的一个子结构,毕竟它只在头插、头删…...
(八十)MySQL是如何基于各种规则去优化执行计划的?(中)
今天我们来讲一下子查询是如何执行的,以及他的执行计划是如何优化的。比如说类似于下面的SQL语句: select * from t1 where x1 (select x1 from t2 where idxxx) 这就是一个典型的子查询 也就是说上面的SQL语句在执行的时候,其实会被拆分为…...
第一章:命题与命题公式
1.命题与命题联结词 1.命题与命题的表示 1. 命题 由一个或几个已知的前提,推导出来一个未知的结论的思维过程称为推理,推理的基本要素就是表达这些前提的一些陈述句,可以将这些陈述句理解为命题。 (1)地球是行星 (2)8不是素数 (3)1 + 2 = 22. 命题真值 一个陈述句不…...
c/c++开发,无可避免的操作符operator(篇一),操作符重载
一、操作符号重载 虽然c/c内置了大量各类操作符,开发者可以很方便将其应用数学运算、成员访问、类型转换、内存分配等执行语句中,但很多时候,也需要根据项目应用需要,通过操作符重载,能够针对类类型的操作数定义不同的…...
【7.MySQL行格式存储】
1.MySQL数据存放文件 我们每创建一个 database(数据库) 都会在 /var/lib/mysql/ 目录里面创建一个以 database 为名的目录,创建一个student表 [rootxiaodainiao ~]#ls /var/lib/mysql/my_test db.opt student.frm student.ibddb.opt:用…...
【Linux】线程实例 | 简单线程池
今天来写一个简单版本的线程池 1.啥是线程池 池塘,顾名思义,线程池就是一个有很多线程的容器。 我们只需要把任务交到这个线程的池子里面,其就能帮我们多线程执行任务,计算出结果。 与阻塞队列不同的是,线程池中内有…...
ATAC-seq 数据分析实战
文章目录一、 ATAC-seq原理和基础知识1. ATAC-seq原理2. Tn5转座子1. 转座概念2. 参与分子1. 转座子(1) 简化的转座子结构(2) Tn5转座子的结构2. 转座酶3. 转座过程二、数据比对和过滤一、 ATAC-seq原理和基础知识 1. ATAC-seq原…...
设计模式-第13章(状态模式)
状态模式状态模式状态模式的好处和用处工作状态状态模式 状态模式(State),当一个对象的内在状态改变时允许改变其行为,这个对象看起来像是改变了其类。 状态模式主要解决的是当控制一个对象状态转换的条件表达式过于复杂时的情况…...
ReentrantLock源码分析(一)加锁流程分析
一、ReetrantLock的使用示例 static ReentrantLock lock new ReentrantLock(); public static void main(String[] args) throws InterruptedException { new Thread(ClassLayOutTest::reentrantLockDemo, "threadA").start(); Thread.sleep(1000);…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...
信息收集:从图像元数据(隐藏信息收集)到用户身份的揭秘 --- 7000
目录 🌐 访问Web服务 💻 分析源代码 ⬇️ 下载图片并保留元数据 🔍 提取元数据(重点) 👤 生成用户名列表 🛠️ 技术原理 图片元数据(EXIF 数据) Username-Anarch…...
链结构与工作量证明7️⃣:用 Go 实现比特币的核心机制
链结构与工作量证明:用 Go 实现比特币的核心机制 如果你用 Go 写过区块、算过哈希,也大致理解了非对称加密、数据序列化这些“硬核知识”,那么恭喜你,现在我们终于可以把这些拼成一条完整的“区块链”。 不过别急,这一节我们重点搞懂两件事: 区块之间是怎么连接成“链”…...


