贪心算法顾名思义在一个贪字上面,它在解决某个问题的时候,总是先从眼前利益出发。也就是说只顾眼前,不顾大局,所以它是局部最优解。它的核心的就是局部最优推出全局最优。 如果我们将所有会议的结束时间从小到大排序。然后从结束时间最小的开始选(局部最优),然后按照这个排序去遍历判断后面是开始时间是否在这之后,如果在则选它,如果不在,则判断下一个是否在。这样是否就能达到最终的最优解?可以尝试举反例来证明它结果的合法性。你会发现在这个场景中,似乎找不到比上述方案的更好的结果了。其实这就是一个贪心算法 贪心算法: 一定会有一个排序,这个就是我们所说的贪心策略,上面问题的策略就是以会议结束时间排序;不同的贪心策略出来结果是不一样,如果结果能被其他举例推翻,那就说明这个策略不合理。 贪心算法不是对所有问题都能得到整体最优解。但是如果经过大量证明成立之后,那么它就是一种高效的算法。如果用贪心来看,这个问题我们似乎只能根据单价来排序了A单价6,B单价5,C单价3,那么我们按排序结果选择,就会选择AB,这个时候我们的价值是16,显然选择AC,价值是18,所以这个贪心策略很容易就被推翻了。
评论星级较低,若资源使用遇到问题可联系上传者,3个工作日内问题未解决可申请退款~
- 1
- 2
前往页