贪心算法.pptx

文档介绍：2020/2/61今天,先汇报比赛2020/2/622020/2/63每周一星(6):06092684 纪元2020/2/64第七讲贪心算法(GreedyAlgorithm)2020/2/65还记得hdoj_1009吗?FatMouse'Trade2020/2/66所谓“贪心算法”是指:在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。2020/2/67特别说明:若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!!2020/2/68用事实说话——2020/2/69实例分析2020/2/610一、事件序列问题已知N个事件的发生时刻和结束时刻(见下表,表中事件已按结束时刻升序排序)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件{2,8,10}。事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长的事件序列。事件编号01234567891011发生时刻130325641081515结束时刻3478910121415181920