贪心算法090420.ppt
《贪心算法090420.ppt》由会员分享,可在线阅读,更多相关《贪心算法090420.ppt(31页珍藏版)》请在三一文库上搜索。
1、ACM程序设计,杭州电子科技大学 刘春英 ,2019/8/19,2,这学期,,你 了吗?,练习,2019/8/19,3,每周一星(8):,qzx,2019/8/19,4,第九讲,贪心算法 (Greedy Algorithm),2019/8/19,5,导引问题:FatMouse Trade,2019/8/19,6,所谓“贪心算法”是指:,在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。,2019/8/19,7,特别说明:,若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果
2、就是最优解!,2019/8/19,8,用事实说话,2019/8/19,9,一、事件序列问题,已知N个事件的发生时刻和结束时刻(见下表,表中事件已按结束时刻升序排序)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件 2,8,10。事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长的事件序列。,2019/8/19,10,算法分析:,不妨用Begini和Endi表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1a2an,满足: Begina1Enda1= BeginanEndan,可以证明,如果在可能的事件a1a2an中选取在时间上不重叠的最长序列,那么一定
3、存在一个包含a1(结束最早)的最长序列。 (证明:略),2019/8/19,11,思考:,请谈谈自己的解题思路,2019/8/19,12,思考题,2037 今年暑假不AC,2019/8/19,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,2019/8
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贪心 算法 090420
链接地址:https://www.31doc.com/p-3377646.html