最先割技术——贪心算法

本文主要是介绍最先割技术——贪心算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心算法

何为“贪心”？

1. 我们看一个找硬币的例子。假设有四种硬币，面值分别为贰角伍分、一角、五分、一分。现在要给顾客找六角三分钱。
   我们下意识里使用了这样的找零算法：
   （1）选出一个面值不超过六角三分的最大面值硬币，即贰角伍分；从六角三分中减去贰角伍分，剩下三角八分。
   （2）选出一个面值不超过三角八分的最大面值硬币，即又一个贰角伍分。
   如此一直做下去。。。
   这种找硬币的方法实际上就是贪心算法，总是作出在当前来看是最好的选择，并不是从整体上最优加以考虑，它所做出的选择只是在某种意义上的局部最优解。

2. 如果问题改变，面值是一分、五分、和一角一分，找给顾客一角五分钱。如果还用贪心算法，我们将找给顾客1个一角一分和4个一分的硬币，然而3个五分的硬币显然是最好的方法。。由此可见，使用贪婪算法未必能得到最优解。

单源最短路径

最小生成树

例1

现有一个数组，元素均为非负整数。假设现在你站在第一个元素上，脚下元素的数字代表当前所能前进的最大步数，请用贪心策略求解能不能走到最后一个元素上。
例如：
A = [3,1,2,4,5] 可以到达最后的元素
B = [1,2,1,0,4] 不能到达最后的元素
试着给出伪代码和时间复杂度。

例2

根据贪心算法的思想，要想最初瓶子水量最少，就需要把最初瓶子里的水一直分给其他空瓶子，最少水量是（a/512).

这篇关于最先割技术——贪心算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---