




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
2023/4/31第三讲贪心算法
(GreedyAlgorithm)2023/4/32导引问题:FatMouse‘Trade(1781)2023/4/33所谓“贪心算法”是指: 在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。2023/4/34特别说明: 若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!!2023/4/35用事实说话——2023/4/36一、事件序列问题
已知N个事件的发生时刻和结束时刻(见下表,表中事件已按结束时刻升序排序)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件{2,8,10}。事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号01234567891011发生时刻130325641081515结束时刻34789101214151819202023/4/37算法分析:不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1<a2<…<an,满足:Begin[a1]<End[a1]<=…<=Begin[an]<End[an]可以证明,如果在可能的事件a1<a2<…<an中选取在时间上不重叠的最长序列,那么一定存在一个包含a1(结束最早)的最长序列。(证明:略)2023/4/38思考题1782
今年暑假不AC2023/4/39二、区间覆盖问题
用i来表示x轴上坐标为[i-1,i]的区间(长度为1),并给出M(1=<M=<200)个不同的整数,表示M个这样的区间。现在让你画几条线段覆盖住所有的区间,条件是:每条线段可以任意长,但是要求所画线段之和最小,并且线段的数目不超过N(1=<N=<50)。例如:M=5个整数1、3、4、8和11表示区间,要求所用线段不超过N=3条012345678910112023/4/310算法分析:如果N>=M,那么显然用M条长度为1的线段可以覆盖住所有的区间,所求的线段总长为M。如果N=1,那么显然所需线段总长为:…如果N=2,相当于N=1的情况下从某处断开(从哪儿断开呢?)。如果N=k呢?2023/4/311三、JLNUOJ_1783MovingTablesSampleInput
3
4
1020
3040
5060
7080
2
13
2200
3
10100
2080
3050
SampleOutput
10
20
30
2023/4/312算法分析:1、如果没有交叉,总时间应该是多少?2、影响搬运时间的因素是什么?3、如果每趟处理都包含最大重叠,处理后的效果是什么?4、得出什么结论?2023/4/313贪心算法的基本步骤
1、从问题的某个初始解出发。2、采用循环语句,当可以向求解目标前进一步时,就根据局部最优策略,得到一个部分解,缩小问题的范围或规模。3、将所有部分解综合起来,得到问题的最终解。2023/4/314思考:田忌赛马(1745)928371748795-200-200-200928371748795-200+200+2002023/4/315Case1:King:200180160Tianji:1901701502023/4/316Case2:King:200180160Tianji:1801701502023/4/317Case3:King:200180160Tianji:1801551502023/4/318总体的思路是什么?本题小结——算法:一:如果田忌的最快的马比齐威王最快的马快,则用它来比,先赢一场;二:如果田忌的最慢的马比齐威王最慢的马快,也用它来比,先赢一场;三:如果不同于前两种情况的任何一种情况都是用田忌的最慢的马来和齐威王最快的马比;先输一场,这叫懂得取舍~~2023/4/3192023/4/320提醒:
很多贪心类型的题目都象本题一样,不是最朴素的贪心,而是需要做一些变化,对于我们,关键是找到贪心的本质!2023/4/321Kruskal在1956年提出了1个最小生成树算法,它的思路很容易理解。设G=(V,E)是一个连通带权图,V={1,2,…,n}。将图中的边按其权值由小到大排序,然后作如下的贪婪选择,由小到大顺序选取各条边,若选某边后不形成回路,则将其保留作为树的一条边;若选某边后形成回路,则将其舍弃,以后也不再考虑。如此依次进行,到选够(n-1)条边即得到最小生成树。最小生成树(1664):例如,对于下图中的带权图各边按权值排序为:d13=1d46=2d25=3d36=4d14=
5d34=5d23=5d12=6d35=6d56=62023/4/322按Kruskal算法选取边的过程如下图所示2023/4/3232023/4/324贪心算法的常见前提操作:
排序!2023/4/325关于排序你在编程中常用的方法?自己写?(基本功)调用排序函数?(方便)常用排序函数qsort()C语言sort()C++2023/4/326关于qsort()头文件:stdlib.h调用示例:intcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}intnum[10]={1,4,7,2,5,8,3,6,9,0};qsort(num,10,sizeof(num[0]),cmp);详细使用方法见论坛帖子——七种qsort排序方法/acm/discuss/thread.php?tid
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 城镇污水管网建设项目建设管理方案(参考)
- xx河流排水防涝设施建设项目质量管理方案(参考范文)
- 2025年非离子型纤维素醚项目合作计划书
- 宪法知识学习题库
- 2025年天猫养车项目发展计划
- 下关穴治疗疼痛的现代技术融合
- 无人驾驶电动拖拉机平台的设计及试验
- 现代泌尿肿瘤学阅读笔记
- 2025年GPS高空探测系统项目发展计划
- 文化旅游的发展
- 2025年贵州省中考语文试卷真题(含答案)
- 2025年广西公需科目答案02
- 人教精通版五年级上学期Lesson25教学课件
- 鲁教版九年级英语课文原文及翻译Unit1
- 《工业固废资源化技术及应用》课程教学大纲
- [北京]输变电工程标准工艺应用图册(图文并茂)
- 2020年雀巢公司北京总部十周年庆典暨雀巢家庭日活动策划案ppt课件
- 1000MW机组锅炉长伸缩式吹灰器检修规程
- 清关发票装箱单样本
- 地下水八大离子-阴阳离子平衡计算公式
- 广州人才绿卡申请表
评论
0/150
提交评论