算法设计与分析 13贪心算法1.ppt

第十三章 贪心算法 ? 贪心算法概念 ? 活动选择问题过程及分析 ? 贪心算法正确性证明 ? 贪心算法的基本内容 贪心算法概念 顾名思义贪心算法总是作出在当前看 来最好的选择也就是说贪心算法并不 从整体最优考虑它所作出的选择只是 在某种意义上的局部最优选择当然 希望贪心算法得到的最终结果也是整体 最优的 活动安排问题 活动安排问题就是要在所给的活动集合 中选出最大的相容活动子集合是可以 用贪心算法