ACM程序设计杭州电子科技大学刘春英******@hdu.*1最近几天,你了吗?ACDate2每周一星(9):qfwrDate3第十讲贪心算法 (GreedyAlgorithm)Date4导引问题:FatMouse'TradeDate5所谓“贪心算法”是指:在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。Date6特别说明:若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!!Date7用事实说话——Date8一、事件序列问题已知N个事件的发生时刻和结束时刻(见下表,表中事件已按结束时刻升序排序)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件{2,8,10}。事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长的事件序列。Date9算法分析:不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1<a2<…<an,满足:Begin[a1]<End[a1]<=…<=Begin[an]<End[an]可以证明,如果在可能的事件a1<a2<…<an中选取在时间上不重叠的最长序列,那么一定存在一个包含a1(结束最早)的最长序列。(证明:略)Date10
c语言(贪心算法) 来自淘豆网m.daumloan.com转载请标明出处.
