贪心的意思

在于在作出选择时，

每次都要选择对自身

最为有利的结果，

保证自身利益的最大化。

贪心算法就是利用

这种贪心思想而得出一种算法。

关于贪心算法，一起来了解！

什么是贪心算法

　　贪心算法（greedy algorithm ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，该算法在每个步骤进行最优选择，试图找到解决整个问题的总体最优方法。

　　贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。贪心算法每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，在一些最优解问题的求解上表现得更简单、更迅速。

算法思路与特点

　　贪心算法一般按如下步骤进行：

　　①建立数学模型来描述问题。

　　②把求解的问题分成若干个子问题。

　　③对每个子问题求解，得到子问题的局部最优解。

　　④把子问题的局部最优解合成原来问题的一个解。

　　贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。

存在问题

　　贪心算法存在如下问题：

　　1.不能保证解是最佳的。

　　2.贪心算法一般用来解决求最大或最小解。

　　3.贪心算法只能确定某些问题的可行性范围。

　　在许多问题中，贪心算法并不会产生最优解，因为贪婪算法没有考虑到所有的数据，当前结果都是基于它前一步的数据而计算出的局部最优结论，缺乏瞻前顾后和统筹全局的能力。所以在贪婪算法失败的问题中，动态规划可能会是更好的选择。

应用实例

　　如果求解问题具有贪婪选择属性与最优子结构属性，则可以使用贪心算法解决。贪婪选择属性是指通过在每个步骤中选择最优选择，可以得到一个全局（总体）最优解。最优子结构是指如果整个问题的最优解包含子问题的最优解，那么问题就有最优子结构。

　　想象我们要进行一场徒步旅行，目标是到达可能的最高峰。在开始之前我们已经有了地图，但是地图上显示了多条可能的路径。我们没有时间去评估每条路径，就采取贪心算法，只选择坡度最大的路径。这似乎是一个很好的远足策略，但它总是最好的吗？旅行结束后，我们再次查看远足地图，可能会发现那里有一条泥泞的河，穿过它就能更容易到达峰顶。这意味着贪心算法总是选择最好的即时路径，而不一定是最终的最佳路径。在优化解决方案方面，这意味着贪婪的解决方案在尝试寻找局部最优解时，可能错过了一个全局最优解。

　　有很多经典的应用，比如霍夫曼编码，普利姆和克鲁斯卡尔最小生成树算法，还有迪杰斯特拉单源最短路径算法，都是使用了这种思维。

　　再例如，平时购物找零钱时，为使找回的零钱的硬币数最少，不要求找零钱的所有方案，而是从最大面值的币种开始，按递减的顺序考虑各面额，先尽量用大面值的面额，当不足大面值时才去考虑下一个较小面值，这就是贪心算法。

（来源：综合科普中国 · 科学百科、全国科学技术名词审定委员会等）