1、什么是贪心算法

贪心算法（greedy algorithm ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

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

对于贪心算法，需要注意以下几个问题。

一旦做出选择，就不可以回溯。
有可能得不到最优解，而是得到最优解的近似解。
选择什么样的贪心策略直接决定算法的好坏。

在遇到具体问题时，有人往往分不清哪些问题能用贪心算法，哪些问题不能用贪心算法。人们经过实践发现，利用贪心算法求解的问题往往具有两个重要的性质：贪心选择和最优子结构。

2、贪心算法的性质

1、贪心选择性质

一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。

最优子结构是指原问题的最优解包含子问题的最优解。贪心算法通过一系列的局部最优解（子问题的最优解）得到全局最优解（原问题的最优解），如果原问题的最优解和子问题的最优解没有关系，则求解子问题没有任何意义，无法采用贪心算法。例如，对于原问题S={a1，a2，…，ai，…，an}，可以在通过贪心选择得到一个当前最优解{ai}之后，转换为求解子问题S?{ai}，继续求解该子问题，最后对所有子问题的最优解进行合并，即可得到原问题的最优解。

3、如何使用贪心算法

1、贪心策略

首先要确定贪心策略，选择当前看上去最好的那个方案。以挑选苹果为例，如果求解目标是越大越好，那么每次就从苹果堆中拿一个最大的苹果，作为局部最优解，贪心策略就是选择当前最大的苹果；如果求解目标是越红越好，那么每次就从苹果堆中拿一个最红的苹果，贪心策略就是选择当前最红的苹果。因此，根据求解目标的不同，贪心策略也会不同。

2．求解过程

根据贪心策略，一步一步地得到局部最优解。例如，首先选择一个最大的苹果，记为a1；然后从剩下的苹果中选择一个最大的苹果，记为a2；以此类推。对所有的局部最优解进行合并，即可得到原问题的最优解{a1，a2，…}。

4、贪心算法存在的问题

贪心算法存在如下问题：

1、不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑；
2、贪心算法一般用来解决求最大或最小解；
3、贪心算法只能确定某些问题的可行性范围。

那像这种算法我们又怎么样应用到实际生活中呢？

5、贪心算法的应用

贪心算法一般用在求最大或最小的情况下。

1、从众多路线中找到最近的道路。比如在出去旅游的时候，需要规划好在一定的假期内怎么样合理的规划路线才能去更多的地方。
2、在生活中，有一堆事情需要去处理。比如在处理事情的时候，需要规划好自己在一定的时间内怎么合理的去做更多的事情。
3、在运送东西的时候，有大量的货物需要运输。比如在运输大量货物的时候，需要规划好自己在一定的空间内，怎样能合理的装下更多的货物。
…