ACM课件贪心算法
32页1、ACM程序设计,杭州电子科技大学 刘春英 ,2020/8/16,2,上一周,,你 了吗?,练习,2020/8/16,3,每周一星(6):,Teddy,2020/8/16,4,第七讲,贪心算法(Greedy Algorithm),2020/8/16,5,还记得FatMouse Trade吗?,2020/8/16,6,所谓“贪心算法”是指:,在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。,2020/8/16,7,特别说明:,若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!,2020/8/16,8,用事实说话,2020/8/16,9,一、事件序列问题,已知N个事件的发生时刻和结束时刻(见下表,表中事件已按结束时刻升序排序)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件 2,8,10。事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长的事件序列。,2020/8/16,10,算法分析:,不妨用Begini和Endi表示事件i的开始
2、时刻和结束时刻。则原题的要求就是找一个最长的序列a1a2an,满足: Begina1Enda1= BeginanEndan,可以证明,如果在可能的事件a1a2an中选取在时间上不重叠的最长序列,那么一定存在一个包含a1(结束最早)的最长序列。 (证明:略),2020/8/16,11,思考:,请谈谈自己的解题思路,2020/8/16,12,思考题,2037 今年暑假不AC,2020/8/16,13,二、区间覆盖问题,用i来表示x轴上坐标为i-1,i的区间(长度为1),并给出M(1=M=200)个不同的整数,表示M个这样的区间。现在让你画几条线段覆盖住所有的区间,条件是:每条线段可以任意长,但是要求所画线段之和最小,并且线段的数目不超过N(1=N=50)。 例如:M=5个整数1、3、4、8和11表示区间,要求所用线段不超过N=3条 0 1 2 3 4 5 6 7 8 9 10 11,2020/8/16,14,算法分析:,如果N=M,那么显然用M条长度为1的线段可以覆盖住所有的区间,所求的线段总长为M。 如果N=1,那么显然所需线段总长为: 如果N=2,相当于N=1的情况下从某处断开(从哪儿
《ACM课件贪心算法》由会员我***分享,可在线阅读,更多相关《ACM课件贪心算法》请在金锄头文库上搜索。
2020届中考英语备考复习-作文课件
2019年中考英语复习-专题十五-交际运用(试卷部分)课件
2019届二轮复习-高中英语-情态动词和虚拟语气课件
2019届一轮复习苏教版物质的跨膜运输课件
2019年北师大版英语单元复习课件::Unit17Laughter课件北师大版选修6
2021届新中考物理冲刺备考复习-力-弹力-重力课件
2019届一轮复习人教版种群的特征和数量变化课件
2020年高考地理一轮复习--等高线地形图-课件
2019版高考英语一轮复习-Unit-1-Living-well课件
2019届一轮复习人教版孟德尔的遗传定律——基因分离定律课件
2019届高三第二轮复习专题二万有引力定律及其应用课件
2020最新部编版语文五年级上册23-鸟的天堂课件含课后练习
2020版高考(浙江)一轮复习:第7讲-细胞呼吸课件
2020年新教材高中英语UNIT4HISTORYANDTRADITIONSSectionⅢDiscoveringUsefulStructures课件必修第二册
2019届高考历史二轮复习阶段三专题十三罗斯福新政与当代资本主义的新变化课件2
2019版高考生物二轮复习-专题三-细胞的生命历程-考点9-细胞分裂过程图像和坐标曲线的识别课件
(通史版)2021版高考历史一轮复习第4部分高考讲座(三)2高考非选择题(12分开放探究题)规范答题讲练课件
2019届高三地理复习第五讲--《区际联系与区域协调发展》课件
2021人教部编版历史九年级上册习题课件:第18课美国的独立
2020学年新教材高中英语Unit1FoodforthoughtPeriodTwoStartingout课件
2024-05-01 21页
2024-05-01 23页
2024-05-01 19页
2024-05-01 30页
2024-05-01 23页
2024-05-01 19页
2024-05-01 23页
2024-05-01 23页
2024-05-01 25页
2024-05-01 23页