本文主要是介绍最先割技术——贪心算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
贪心算法
何为“贪心”？
-
我们看一个找硬币的例子。假设有四种硬币，面值分别为贰角伍分、一角、五分、一分。现在要给顾客找六角三分钱。
我们下意识里使用了这样的找零算法：
（1）选出一个面值不超过六角三分的最大面值硬币，即贰角伍分；从六角三分中减去贰角伍分，剩下三角八分。
（2）选出一个面值不超过三角八分的最大面值硬币，即又一个贰角伍分。
如此一直做下去。。。
这种找硬币的方法实际上就是贪心算法，总是作出在当前来看是最好的选择，并不是从整体上最优加以考虑，它所做出的选择只是在某种意义上的局部最优解。 -
如果问题改变，面值是一分、五分、和一角一分，找给顾客一角五分钱。如果还用贪心算法，我们将找给顾客1个一角一分和4个一分的硬币，然而3个五分的硬币显然是最好的方法。。由此可见，使用贪婪算法未必能得到最优解。
单源最短路径
最小生成树
例1
现有一个数组，元素均为非负整数。假设现在你站在第一个元素上，脚下元素的数字代表当前所能前进的最大步数，请用贪心策略求解能不能走到最后一个元素上。
例如：
A = [3,1,2,4,5] 可以到达最后的元素
B = [1,2,1,0,4] 不能到达最后的元素
试着给出伪代码和时间复杂度。
例2
根据贪心算法的思想，要想最初瓶子水量最少，就需要把最初瓶子里的水一直分给其他空瓶子，最少水量是（a/512).
这篇关于最先割技术——贪心算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
