【算法】动态规划之背包DP问题(2024.5.11)

 前言:

本系列是学习了董晓老师所讲的知识点做的笔记

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)

动态规划系列 

【算法】动态规划之线性DP问题-CSDN博客

01背包

步骤:

分析容量j与w[i]的关系,然后分析是否要放入背包

二维数组

for(int i=1; i<=n; i++)       //物品for(int j=1; j<=m; j++)     //容量if(j<w[i]) f[i][j]=f[i-1][j];            else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);

一维数组用逆序循环的原因

用一维数组f[i]只记录一行数据,让j值顺序循环,顺序更新f[j]值,f[j-w[i]]会先于f[j]更新,会出错。

如果j是逆序循环,f[j]会先于f[j-w[i]]更新

01背包使用的是上一层的值,如果顺序循环的话就会改变应有的值

for (int i = 1; i <= n; i++)//物品i
{for (int j = m; j >= w[i], j--)//容量j{f[j] = max(f[j], f[j - w[i]] + c[i])}
}
 

完全背包 

完全背包使用的是同一层的值,顺序循环的话改变值正是他所需要的,所以他可以顺序循环

for(int i=1; i<=n; i++)       //物品for(int j=1; j<=m; j++)     //容量if(j<w[i]) f[i][j]=f[i-1][j];            else f[i][j]=max(f[i-1][j],f[i][j-w[i]]+c[i]);
for (int i = 1; i <= n; i++)//物品i
{for (int j = w[i]; j <= m, j++)//容量j{f[j] = max(f[j], f[j - w[i]] + c[i])}
}

01背包和完全背包的区别

01背包第i件物品可以放入0个或者1个

完全背包第i件物品可以放入0个,1个,2个..... 

多重背包

01背包:第i种物品可以取0件、取1件。

多重背包:第i种物品可以取0件、取1件、取2件……取s件。

多重背包转化为01背包求解:把第i种物品换成s件01背包中的物品,每件物品的体积为k*v,价值为k*w(0≤k≤s)。

朴素算法

  //v[i],&w[i],&s[i])分别表示体积,价值,数量for(int i=1; i<=n; i++)               for(int j=0; j<=m; j++)               for(int k=0; k<=s[i]&&k*v[i]<=j; k++) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

二进制优化

int num = 1;
for (int i = 1; i <= n; i++)
{cin >> v >> w >> s;//体积,价值,数量for (j = 1; j <= s; j <<= 1){vv[num] = j * v;ww[num++] = j * w;s -= j;}if (s){vv[num] = s * v;ww[num++] = s * w;}
}
for (int i = 1; i < num; i++)for (int j = m; j >= v[i]; j--)f[j] = max(f[j], f[j - vv[i]] + ww[i]);

单调队列

前置知识 

【算法】用存入下标的方法来巧解单调队列-CSDN博客

 

(k-q[h])/v是还能放入物品的个数。f[k]=窗口中的最大值+还能放入物品的价值。 

混合背包 

题目:

思路

分类处理的思想:
1.利用多重背包的二进制优化,将多重背包转化为多个01背包。
2.用a,b,c三个数组来记录转化之后的所有背包的体积、价值、类型,c[i]==0表示完全背包,c[i]==1表示01背包。最后再做一遍,以c的值分为两类,做完全背包和01背包。

for (int i = 1; i <= n; i++) {scanf("%d%d%d", &v, &w, &s);if (s == 0) {     //完全背包a[num] = v;b[num] = w;c[num++] = 0; //背包类型 }else {         if (s == -1)s = 1;//01背包转多重背包int k = 1;while (s >= k) {//二进制拆分a[num] = k * v;b[num] = k * w;c[num++] = 1;s -= k; k <<= 1;}if (s) {a[num] = s * v;b[num] = s * w;c[num++] = 1;}}
}
for (int i = 1; i < num; i++) {if (c[i] == 1) //01背包for (int j = m; j >= a[i]; j--)f[j] = max(f[j], f[j - a[i]] + b[i]);else        //完全背包for (int j = a[i]; j <= m; j++)f[j] = max(f[j], f[j - a[i]] + b[i]);
}

二维费用背包 

f[i][k]: 背包容量为j,且承重为k时,能放入的最大价值。

f[V][M]: 背包容量为V,且承重为M时能放入的最大价值,即全局最优解。

  cin>>n>>V>>M;for(int i=1; i<=n; i++){  //物品 cin>>v>>m>>w;for(int j=V; j>=v; j--) //体积for(int k=M; k>=m; k--) //重量f[j][k]=max(f[j][k],f[j-v][k-m]+w);
}cout<<f[V][M];

分组背包

分组背包与多重背包的区别是分组背包在每一个组中只能选一个 

决策在前,体积在后的方法是错误的(用同一组的物品来更新了),积前策后才是对的

二维决策:同一个组里面的物品只能选一个

一维决策:个数

for (int i = 1; i <= n; i++)     //物品组
for (int j = 1; j <= V; j++)     //体积
for (int k = 0; k <= s[i]; k++)  //决策
if (j >= v[i][k])
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
for (int j = 1; j <= s; j++) 
cin >> v[j] >> w[j];
for (int j = V; j >= 1; j--) //体积
for (int k = 0; k <= s; k++) //决策
if (j >= v[k]) f[j] = max(f[j], f[j - v[k]] + w[k]);

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/324818.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OGG几何内核开发-BRepAlgoAPI_Fuse与BRep_Builder.MakeCompound比较

最近在与同事讨论BRepAlgoAPI_Fuse与BRep_Builder.MakeCompound有什么区别。 一、从直觉上来说&#xff0c;BRepAlgoAPI_Fuse会对两个实体相交处理&#xff0c;相交的部分会重新的生成相关的曲面。而BRep_Builder.MakeCompound仅仅是把两个实体组合成一个新的实体&#xff0c;…

JUC下的BlockingQueue详解

BlockingQueue是Java并发包(java.util.concurrent)中提供的一个接口&#xff0c;它扩展了Queue接口&#xff0c;增加了阻塞功能。这意味着当队列满时尝试入队操作&#xff0c;或者队列空时尝试出队操作&#xff0c;线程会进入等待状态&#xff0c;直到队列状态允许操作继续。这…

https://是怎么实现的?

默认的网站建设好后都是http访问模式&#xff0c;这种模式对于纯内容类型的网站来说&#xff0c;没有什么问题&#xff0c;但如果受到中间网络劫持会让网站轻易的跳转钓鱼网站&#xff0c;为避免这种情况下发生&#xff0c;所以传统的网站改为https协议&#xff0c;这种协议自己…

信息检索(35):LEXMAE: LEXICON-BOTTLENECKED PRETRAINING FOR LARGE-SCALE RETRIEVAL

LEXMAE: LEXICON-BOTTLENECKED PRETRAINING FOR LARGE-SCALE RETRIEVAL 标题摘要1 引言2 相关工作3 LEXMAE&#xff1a;词典瓶颈屏蔽自动编码器3.1 语言建模编码器3.2 词典瓶颈模块3.3 弱化掩蔽式解码器3.4 词汇加权检索器的预训练目标和微调 4 实验4.1 主要评估4.2 效率分析与…

利用OpenShift的ImageStream部署临时版本

公司是港企&#xff0c;项目都部署在OpenShift上统一管理&#xff0c;因为运行环境为香港网络(外网)&#xff0c;配置、中间件等大陆无法直接访问联通。因此在大陆开发时&#xff0c;测试是个很大的问题。为了避免往Git上频繁提交未确定可用的版本&#xff0c;选择用利用OpenSh…

机器人系统仿真

0、何为仿真 通过计算机对实体机器人系统进行模拟的技术。 1、为何仿真 低成本&#xff1a; 机器人实体一般价格昂贵&#xff0c;为降低机器人学习、调试的成本&#xff1b;高效&#xff1a; 搭建的环境更为多样且灵活&#xff0c;可以提高测试效率以及测试覆盖率&#xff1b…

【python】python中的argparse模块,教你如何自定义命令行参数

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…

谁使用DITA?

▲ 搜索“大龙谈智能内容”关注公众号▲ Keith根据LinkedIn上的数据进行的统计&#xff0c;主要反应的西方世界使用DITA的公司。因为LinkedIn在国内不能访问&#xff0c;笔者认为针对中国的数据并不准确。 作者 | John Walker - NXP销售和市场营销业务分析师 2013年4月18日 …

栈实现队列

一、分析 栈的特点是先出再入&#xff0c;而队列的特点为先入先出&#xff0c;所以我们创造两个栈&#xff0c;一个用来存放数据&#xff0c;一个用来实现其它功能此时栈顶为队尾&#xff1b;当要找队头数据时将前n-1个数据移入到另一个栈中&#xff0c;此时剩余那个数据为队头…

ASP.NET网上图书预约系统的设计

摘 要 《网上图书预约系统的设计》是以为读者提供便利为前提而开发的一个信息管理系统&#xff0c;它不仅要求建立数据的一致性和完整性&#xff0c;而且还需要应用程序功能的完备、易用等特点。系统主要采用VB.NET作为前端的应用开发工具&#xff0c;利用SQL Server2000数据…

做题杂记666

[XYCTF2024] 铜匠 题目描述&#xff1a; from Crypto.Util.number import * from secrets import flagm bytes_to_long(flag) m1 getRandomRange(1, m) m2 getRandomRange(1, m) m3 m - m1 - m2def task1():e 149p getPrime(512)q getPrime(512)n p * qd inverse(e,…

VTK官方示例

VTK官方示例 -vtk字體 #!/usr/bin/env python# noinspection PyUnresolvedReferences import vtkmodules.vtkInteractionStyle # noinspection PyUnresolvedReferences import vtkmodules.vtkRenderingFreeType # noinspection PyUnresolvedReferences import vtkmodules.vtk…

Java - Json字符串转List<LinkedHashMap<String,String>>

需求&#xff1a;在处理数据时&#xff0c;需要将一个Object类型对象集合转为有序的Map类型集合。 一、问题 1.原代码&#xff1a; 但在使用时出现报错&#xff1a; Incompatible equality constraint: LinkedHashMap<String, String> and LinkedHashMap 不兼容的相等…

【软考】模拟考卷错题本2024-05-11

1 设计模式- 适配器模式 基本上上述的图解已经涵盖了绝大多数主流的设计模式和其特点。理解记忆下即可&#xff0c;这里对下午的考题也有帮助的。 2 计算机组成原理 cpu 访问速度 这个真的是憨憨咯~看到内存就选内存&#xff0c;题目都没审好。这里的速度比cpu内部的要比外部的…

【C语言】动态内存管理

一、为什么有动态内存分配 在进入正文前&#xff0c;我们简单了解一下变量在内存中的位置&#xff08;在最后具体讲&#xff09;&#xff1a; 函数形参&#xff0c;局部变量&#xff1a;栈区 动态开辟的空间&#xff1a;堆区 全局变量&#xff0c;静态变量&#xff08;static修…

【QVariant类型剖析】

QVariant类型剖析 &#x1f31f; 官方文档中给出的定义&#x1f31f; 特性&#x1f338;QVariant实战应用&#x1f338;项目成果展示 &#x1f31f; 官方文档中给出的定义 &#x1f4d8;Because C forbids unions from including types that have non-default constructors or…

Rancher-Kubewarden-保姆级教学-含Demo测试

一、什么是Kubewarden&#xff1f; What is Kubewarden? | Kubewarden 1、就是容器集群的准入策略引擎。 1、使用的策略其实就是k8s原生的security context. 2、使用WebAssembly来编写策略。 1、WebAssembly&#xff0c;可以使用擅长的开发语言来编写策略。&#xff08;下面的…

SVM直观理解

https://tangshusen.me/2018/10/27/SVM/ https://www.bilibili.com/video/BV16T4y1y7qj/?spm_id_from333.337.search-card.all.click&vd_source8272bd48fee17396a4a1746c256ab0ae SVM是什么? 先来看看维基百科上对SVM的定义: 支持向量机&#xff08;英语&#xff1a;su…

【Linux系列】file命令

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

Kafka效率篇-提升效率三板斧

kafka在效率上做了很多的努力。最初的一个使用场景是处理网页上活跃的数据&#xff0c;它往往有非常大的体量&#xff0c;每个页面都能产生数十条写入。而且我们假设每条消息都会被至少一个消费者消费&#xff08;通常是多个&#xff09;&#xff0c;因此&#xff0c;我们努力让…