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

数据结构与算法之贪心动态规划

        一:思考

        1.某天早上公司领导找你解决一个问题,明天公司有N个同等级的会议需要使用同一个会议室,现在给你这个N个会议的开始和结束 时间,你怎么样安排才能使会议室最大利用?即安排最多场次的会议?电影的话 那肯定是最多加票价最高的,入场率。综合算法

        2.双十一马上就要来了,小C心目中的女神在购物车加了N个东西,突然她中了一个奖可以清空购物车5000元的东西(不能找零),每个东西只能买一件,那么她应该如何选择物品使之中奖的额度能最大利用呢?如果存在多种最优组合你只需要给出一种即可,嘿嘿 现在女神来问你,你该怎么办?(动态规划)

        二: 贪心算法

        概念:贪心算法又叫做贪婪算法,它在求解某个问题是,总是做出眼前最大利益。 也就是说只顾眼前不顾大局,所以它是局部最优解。核心点:通过局部最优推出全局最优

        举例:

        1.某天早上公司领导找你解决一个问题,明天公司有N个同等级的会议需要使用同一个会议室,现在给你这个N个会议的开始和结束时间,你怎么样安排才能使会议室最大利用?即安排最多场次的会议?

         现在我们怎么去贪?也就这个我们选择的贪心策略:、

         1.1 选时间最短:1-3,2~4,3~5,4~6

        1.2 按结束时间从小到大排序:首先把第一个加入我们可以开会的列表。之后只要开始时间是大于我们上一个的结束时间的就可以开 (代码如下)

package tx;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** 贪心算法:1.某天早上公司领导找你解决一个问题,明天公司有N个同等级的会议需要使用同一个会议室,* 	现在给你这个N个会议的开始和结束时间,你怎么样安排才能使会议室最大利用?即安排最多场次的会议?** 	策略:按结束时间从小到大排序:首先把第一个加入我们可以开会的列表。之后只要开始时间是大于我们上一个的结束时间的就可以开* 	核心:排序*/
class Metting implements Comparable<Metting> {int meNum; // 编号int startTime; // 开始时间int endTime; // 结束时间public Metting(int meNum, int startTime, int endTime) {super();this.meNum = meNum;this.startTime = startTime;this.endTime = endTime;}public int compareTo(Metting o) {if (this.endTime > o.endTime)return 1;return -1;}@Overridepublic String toString() {return "Metting [meNum=" + meNum + ", startTime=" + startTime+ ", endTime=" + endTime + "]";}}public class MettingTest {public static void main(String[] args) {Scanner cin = new Scanner(System.in);List<Metting> mettings = new ArrayList<Metting>();int n = cin.nextInt();	//n个会议for (int i = 0 ;i < n; i++){int start = cin.nextInt();int end = cin.nextInt();Metting metting = new Metting(i+1, start, end);mettings.add(metting);}mettings.sort(null);int curTime = 0;		//当前的时间,从一天的0点开始,如果领导要求从8点开始 那curTime=8for(int i = 0 ; i < n; i ++){Metting metting = mettings.get(i);if(metting.startTime >= curTime){		//会议的开始时间比我们当前的要大 表示可以开System.out.println(metting.toString());curTime = metting.endTime;}}}
}

         2.1 贪心算法的核心思想

        贪心算法的套路:一定会有一个排序。哈夫曼编码,贪心算法,压缩算法。最短路径

        贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

         贪心算法其最重要的两个点就是: 贪心策略排序

通过局部最优解能够得到全局最优解

一般通过以下问题就可以通过贪心算法解决:

                1.针对某个问题有限制值,以及有一个期望的最好结果,通常是从某些数据中选出其中一些,达到最好的结果。

                2.一般会有一个排序,找出贡献最大的。

                3.举例看贪心是否可以解决。 一般用在任务调度,教师排课等系统。 实际上,用贪心算法解决问题的思路,并不总能给出最优解。

        三:动态规划

        经典问题

        背包问题 小偷去某商店盗窃,背有一个背包,容量是5kg,现在有以下物品(物品不能切分,且只有一个),请问小偷应该怎么拿才能得到最大的价值?

5kg的袋子

物品:

钱:6  10  12

Kg:1  2   4

思路:我们把5kg的袋子,拆分成1kg,1kg这样子计算,里面的表格就表示当前重量下能装的最多的钱。表格的数列就表示是要装的物品

1kg

2kg

3kg

4kg

5kg

加入物品1

6

6

6

6

6

加入物品2

6

10

10+6=16

10+6=16

16

加入物品3

6

10

16

16

18

第一个物品: 袋子只能装1kg的物品,所以价钱为6

第二个物品: 

        袋子当前为1kg 的容量时,我们发现物品2装不进去。那我们应该取多少呢?是不是只要取物品进来时1kg最大钱?

        当袋子为2kg时,我们发现物品2可以装下去,此时可以得到10块钱,之前物品1进来时2kg最大是6吧,那我们肯定要选择大的这个10,而不是6.此时袋子还剩0kg可以装。

        袋子为3kg时,我们还是可以装下这个物品2,得到10块,袋子还剩下1kg。

10+1kg能装的东西。

第三个物品:

        袋子为4kg时,物品3可以转进来,得到12块钱,袋子还剩0kg。

        我发现我不装物品3 还能得到16呢

        袋子为5kg时,物品3可以转进来,得到12块钱,袋子还剩1kg。那么装了物品3就能得到12+6=18块钱

        我发现我不装物品3 能得到16,比18小,所以决定装.。

                                (图解:将数值除以10就是上面的题)

                代码实现

package tx;public class Dp {public static void main(String[] args) {int value [] ={60,100,120};int weigth[] = {10,20,40};	//购物车那个问题 只需要一个价值就行了,重量都都没有。int w = 50;  //代表我可以装的数量int n = 3; //代表三个物品int dp[][] = new int[n+1][w+1];		//n表示是物品,w表示重量,初始化全是0for(int i = 1; i<= n; i++){	//每次加的物品for(int cw = 1 ; cw <= w ; cw ++){		//分割的背包if(weigth[i - 1] <= cw){		//表示这个物品可以装进去dp[i][cw] = Math.max(value[i-1] + dp[i-1][cw-weigth[i-1]],dp[i-1][cw]);}else{dp[i][cw] = dp[i-1][cw];	//不能装}}}System.out.println(dp[n][w]);}
}

四:动归和贪心的比较        

        贪心是只管眼前不会管后的情况,而动归不一样,它的每次递推都是基于上一次的最优解进行。所以往往动归是一定能求出最优解的,而贪心不一定,这也是贪心算法的缺点,但是大家都看到了动归的时间复杂度是O(n*m)而贪心是O(nlogn),所以贪心算法的是高效的,动归如果子问题太多的话 就容易算不出结果,而且能用动归的问题往往用贪心都能解决一部分,甚至很大一部分。因此如果在实际项目中要求不是特别严的话 我建议使用贪心算法求最优解,其实我们很多时候并不用保证100%的准确,能尽量准确就可以了,贪心恰恰是符合这个规则的。

        五:购物车代码实现

package tx;public class CardDp {public static void main(String[] args) {int weigth[] = {1,2,3,4,5,9};	//购物车那个问题 只需要一个价值就行了,重量都都没有。int w = 8;int n = 6;int dp[][] = new int[n+1][w+1];		//n表示是物品,w表示重量,初始化全是0for(int i = 1; i<= n; i++){	//每次加的物品for(int cw = 1 ; cw <= w ; cw ++){		//分割的背包if(weigth[i - 1] <= cw){		//表示这个物品可以装进去dp[i][cw] = Math.max(weigth[i-1] + dp[i-1][cw-weigth[i-1]],dp[i-1][cw]);}else{dp[i][cw] = dp[i-1][cw];	//不能装}}}System.out.println(dp[n][w]);}
}

相关文章:

数据结构与算法之贪心动态规划

一&#xff1a;思考 1.某天早上公司领导找你解决一个问题&#xff0c;明天公司有N个同等级的会议需要使用同一个会议室&#xff0c;现在给你这个N个会议的开始和结束 时间&#xff0c;你怎么样安排才能使会议室最大利用&#xff1f;即安排最多场次的会议&#xff1f;电影的话 那…...

【网络编程】网络基础概念

(꒪ꇴ꒪ )&#xff0c;Hello我是祐言QAQ我的博客主页&#xff1a;C/C语言&#xff0c;数据结构&#xff0c;Linux基础&#xff0c;ARM开发板&#xff0c;网络编程等领域UP&#x1f30d;快上&#x1f698;&#xff0c;一起学习&#xff0c;让我们成为一个强大的攻城狮&#xff0…...

连接虚拟机报错 Could not connect to ‘192.168.xxx.xxx‘ (port 22): Connection failed.

使用xshell连接虚拟机报错 Connecting to 192.168.204.129:22… Could not connect to ‘192.168.204.129’ (port 22): Connection failed. Type help’ to learn how to use Xshell prompt. 按网上的方法 是否能ping通内外网 ping www.baidu.com防火墙是否关闭 firewal…...

数学建模--Topsis评价方法的Python实现

目录 1.算法流程简介 2.算法核心代码 3.算法效果展示 1.算法流程简介 """ TOPSIS(综合评价方法):主要是根据根据各测评对象与理想目标的接近程度进行排序. 然后在现有研究对象中进行相对优劣评价。 其基本原理就是求解计算各评价对象与最优解和最劣解的距离…...

超越时间与人力的软件开发智慧:《人月神话》

目录 1、写在前面2、沟通&#xff01;沟通&#xff01;沟通&#xff01;3、“银弹论”4、“人月神话”不能成立的原因5、影响力6、图书推荐 1、写在前面 《人月神话》是由计算机科学家弗雷德里克布鲁克斯所著的一本经典著作&#xff0c;首次出版于1975年。这本书以一个个小故事…...

Java Stream 流对象(实用技巧)

目录 一、InputStream & OutputStream 1.1、InputStream 和 OutputStream 一般使用 1.2、特殊使用 1.2.1、如何表示文件读取完毕&#xff1f;&#xff08;DataInputStream&#xff09; 1.2.2、字符读取/文本数据读取&#xff08;Scanner&#xff09; 1.2.3、文件的随机…...

【用unity实现100个游戏之8】用Unity制作一个炸弹人游戏

文章目录 前言素材开始一、绘制地图二、玩家设置三、玩家移动四、玩家四方向动画运动切换 五、放置炸弹六、生成爆炸效果七、墙壁和可破坏障碍物的判断八、道具生成和效果九、玩家死亡十、简单的敌人AI十一、简单敌人AI十二、随机绘制地图十三、虚拟摇杆 最终效果待续源码完结 …...

简易版人脸识别qt opencv

1、配置文件.pro #------------------------------------------------- # # Project created by QtCreator 2023-09-05T19:00:36 # #-------------------------------------------------QT core guigreaterThan(QT_MAJOR_VERSION, 4): QT widgetsTARGET 01_face TEMP…...

如何系统地学习 JavaScript?

前言 在学习JavaScript前需要先将Html和Css的相关知识点弄清楚&#xff0c;Js的很多操作是要结合Html和Css&#xff0c;下面我总结了Html、Css和Js的相关学习知识点供参考&#xff0c;希望对你有所帮助喔~ Html 文档学习 【HTML 】w3school教程 :https://www.w3school.com.…...

对称二叉树(Leetcode 101)

题目 101. 对称二叉树 思路 使用层序遍历&#xff0c;遍历当前层的节点时&#xff0c;如该节点的左&#xff08;右&#xff09;孩子为空&#xff0c;在list中添加null&#xff0c;否则加入左&#xff08;右&#xff09;孩子的值。每遍历完一层则对当前list进行判断&#xff0c…...

动手学深度学习(2)-3.5 图像分类数据集

文章目录 引言正文图像分类数据集主要包介绍主要流程具体代码练习 总结 引言 这里主要是看一下如何加载数据集&#xff0c;并且生成批次训练的数据。最大的收获是&#xff0c;知道了如何在训练阶段提高模型训练的性能 增加batch_size增加num_worker数据预加载 正文 图像分类…...

C标准输入与标准输出——stdin,stdout

&#x1f517; 《C语言趣味教程》&#x1f448; 猛戳订阅&#xff01;&#xff01;&#xff01; ​—— 热门专栏《维生素C语言》的重制版 —— &#x1f4ad; 写在前面&#xff1a;这是一套 C 语言趣味教学专栏&#xff0c;目前正在火热连载中&#xff0c;欢迎猛戳订阅&#…...

如何将home目录空间扩充到根目录下

目录 1、查看查看磁盘使用情况2、扩容思路3、卸载并删除/home4、扩大/root逻辑卷5、扩大/文件系统6、重建/home逻辑卷7、创建/home文件系统8、将新建的文件系统挂载到/home目录下9、恢复/home并删除备份10、再次查看看磁盘存储 系统&#xff1a;centos7.9 1、查看查看磁盘使用…...

Ceph PG Peering数据修复

ceph数据修复 当PG完成了Peering过程后&#xff0c;处于Active状态的PG就可以对外提供服务了。如果该PG的各个副本上有不一致的对象&#xff0c;就需要进行修复。 Ceph的修复过程有两种&#xff1a;Recovery和Backfill。 Recovery是仅依据PG日志中的缺失记录来修复不一致的对…...

服务器上使用screen和linux的基本操作

临时换源 pip install torch1.7.1 -i https://pypi.tuna.tsinghua.edu.cn/simple some-package pip install torch1.7.1 -i http://pypi.douban.com/simple some-package临时清华源和豆瓣源 配环境的一点小问题 我们尽量是去配置能满足代码的环境&#xff0c;而不要想着修改…...

Kafka3.0.0版本——文件存储机制

这里写木目录标题 一、Topic 数据的存储机制1.1、Topic 数据的存储机制的概述1.2、Topic 数据的存储机制的图解1.3、Topic 数据的存储机制的文件解释 二、Topic数据的存储位置示例 一、Topic 数据的存储机制 1.1、Topic 数据的存储机制的概述 Topic是逻辑上的概念&#xff0c…...

Linux如何安装MySQL

Linux安装MySQL5.7 1、下载 官网下载地址&#xff1a;http://dev.mysql.com/downloads/mysql/ 2、复制下面几个文件 3、检查当前系统是否安装过mysql、检查当前mysql依赖环境、检查/tmp文件夹权限 1&#xff09;检查当前系统是否安装过mysql&#xff0c;执行安装命令前&am…...

确保网络的安全技术介绍

防火墙技术 防火墙是隔离本地网络与外界网络的一道防御系统。通常用于内部局域网 与外部广域网之间&#xff0c;通过限制外部网络用户以非法手段来访问内部资源&#xff0c;来达到保 护内部网络的安全。根据安全规则&#xff0c;防火墙对任何外部网络访问内部网络的行为进 …...

机器学习练习

原文章添加链接描述...

算法通关村第十九关——最小路径和

LeetCode64. 给定一个包含非负整数的 m n 网格 grid,请找出一条从左上角到右下角的路径&#xff0c;使得路径上的数字总和为最小。 输入&#xff1a;grid[[1,3,1],[1,5,1],[4,2,1]] 输出&#xff1a;7 解释&#xff1a;因为路径1→3→1→1→1的总和最小。 public int minPath…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...