下载此文档

acm程序设计贪心算法.ppt

文档分类：IT计算机 | 页数：约31页举报非法文档有奖

1/31

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/31 下载此文档

文档列表 文档介绍

ACM程序设计**这学期,你了吗?练****每周一星(8):qzx**第九讲贪心算法(GreedyAlgorithm)**导引问题:FatMouse'Trade**所谓“贪心算法”是指:在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。**特别说明:若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!!**用事实说话——**一、事件序列问题已知N个事件的发生时刻和结束时刻(见下表,表中事件已按结束时刻升序排序)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件{2,8,10}。事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号01234567891011发生时刻130325641081515结束时刻3478910121415181920**算法分析:不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1<a2<…<an,满足:Begin[a1]<End[a1]<=…<=Begin[an]<End[an]可以证明,如果在可能的事件a1<a2<…<an中选取在时间上不重叠的最长序列,那么一定存在一个包含a1(结束最早)的最长序列。(证明:略)

acm程序设计贪心算法来自淘豆网www.taodocs.com转载请标明出处.