江苏龙网

  1. 主页 > 生活百科 > >

贪心算法

贪心算法

定义

贪心算法

文章插图
贪心算法是指每一步都求最优解，迭代求得可能是全局最优解的算法 。当然局部最优解可能不是全局最优解，也可能是全局最优解，这就要看选择的贪心策略了 。一般证明选择的策略是正确的，可以使用数学归纳法来证明，一般证明较难，可以写一个暴力的方式求得最优解，然后试不同的贪心策略，看哪一种正确即可，这个就是对数器的思路 。
对数器就是通过大量的测试数据来验证算法是否正确的方式 。
对数器核心部件有两个：
  • 绝对正确的方法
  • 能产生大量随机样例的随机发生器
贪心算法举例开最多的会议题目： 给定每一个会议开始的时间和结束的时间，怎么安排会议要求会
议室进行的会议的场次最多 。返回这个最多的会议场次 。
贪心策略：根据哪个项目早结束安排哪个
代码：
贪心算法

文章插图
 

贪心算法

文章插图
 
总结贪心算法，因为是要选一种局部最优解，要么选最大值，要么选最小值 。所以基本上贪心算法都可以使用到堆的结构来解决 。多做几道贪心算法的题就有感觉了 。

【贪心算法】


    推荐阅读


    上一篇：怎么煮绿豆汤

    下一篇：玩游戏卡怎么办