贪心算法

导论：

?小孩子吃糖果，总是想要多多的；吃水果，总是想要最大的；买玩具，总是想要最好的；这些东西是与生俱来的。对美好事物的趋优性，就像植物的趋光性，”良禽择木而栖，贤臣择主而事“”窈窕淑女，君子好逑“，我们似乎永远在追求美而优的东西。现实中的很多事情，正是因为趋优性才使我们的生活一步一步走向美好。

一：贪心本质

贪心算法正是”活在当下，看清楚眼前“的办法。贪心算法从问题的初始解开始，一步一步的做出当前最好的选择，逐步逼近问题的目标，从而尽可能地得到最优解，即使达不到最优解，也可以得到最优解地近似解。

贪心算法在解决问题地策略上”目光短浅“。贪心算法只根据当前信息做出选择，而且一旦做出选择，则不管将来有什么结果，这个选择都不会改变。换言之，贪心算法并不是从整体上做最优考虑，它所做出地选择只是某种意义上的局部最优。在实际应用中，很多问题都可以通过贪心算法得到最优解或最优解的近似解。

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

（1）一旦做出选择，就不可以回溯

（2）有可能得不到最优解，而是得到最优解的近似解

（3）选择什么样的贪心策略直接决定算法的好坏?

二：贪亦有道?

（1）贪心选择

贪心选择是指原问题的整体最优解可以通过一系列局部最优的选择得到：先做出当前最优的选择，将原问题变为一个相似却规模更小的子问题，而后的每一步都是当前最优的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。

（2）最优子结构?

最优子结构是指原问题的最优解包含子问题的最优解。贪心算法通过一系列的局部最优解（子问题的最优解）得到全局最优解（原问题得最优解），如果原问题得最优解和子问题得最优解没有关系，则求解子问题没有任何意义，无法采用贪心算法。

三：贪心算法秘籍?

（1）贪心策略

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