贪心算法

     前面小编主要分享了使用到分治策略的经典排序算法，接下来小编要来分享下另外一个经典的算法，也就是贪心算法。贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。这些算法后续小编都会进行分享，今天小编先简单介绍下什么是“贪心算法”。

一、贪心本质

    我们经常会听到这些话：“人要活在当下”，“看清楚眼前”……。贪心算法正是“活在当下，看清楚眼前”的办法，从问题的初始解开始，一步一歩地做出当前最好的选择，逐步逼近问题的目标，尽可能地得到最优解，即使达不到最优解，也可以得到最优解的近似解。

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

    在贪心算法中，我们需要注意以下几个问题

    （1）没有后悔药。一旦做出选择，不可以反悔

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

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

二、贪心算法遵循的原则

    那么，贪心算法需要遵循什么样的原则呢？

    “君子爱财，取之有道”，我们在贪心算法中“贪亦有道”。通常我们在遇到具体问题时，往往分不清哪些问题该用贪心策略求解，哪些问题不能使用贪心策略。经过实践我们发现，利用贪心算法求解的问题往往具有两个重要的特性：贪心选择性质和最优子结构性质。如果满足这两个性质就可以使用贪心算法了。

    （1）贪心选择

    所谓贪心选择性质是指原问题的整体最优解可以通过一系列局部最优的选择得到。应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。运用贪心策略解决的问题在程序的运行过程中无回溯过程。

    （2）最优子结构

    当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题是否可用贪心算法求解的关键。例如原问题S={a1，a2，…，ai，…，an}，通过贪心选择选出一个当前最优解{ai}之后，转化为求解子问题S−{ai}，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。其实就是所谓的集合中的包含关系。

三、贪心算法秘籍

    武林中有武功秘籍，算法中也有贪心秘籍。上面我们已经知道了具有贪心选择和最优子结构性质就可以使用贪心算法，那么如何使用呢？下面介绍贪心算法秘籍。

    （1）贪心策略

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

    （2）局部最优解

    根据贪心策略，一步一步地得到局部最优解。例如，第一次选一个最大的苹果放起来，记为a1，第二次再从剩下的苹果堆中选择一个最大的苹果放起来，记为a2，以此类推。

    （3）全局最优解

    把所有的局部最优解合成为原来问题的一个最优解（a1，a2，…）。

    怎么有点儿像冒泡排序啊？

    其实不是贪心算法像冒泡排序，而是冒泡排序使用了贪心算法，它的贪心策略就是每一次从剩下的序列中选一个最大的数，把这些选出来的数放在一起，就得到了从大到小的排序结果。

四、例子简析之货币选择问题

    问题描述：分别有1,5,10,50,100元，分别有5,2,2,3,5张纸币。问若要支付k元，则需要多少张纸币？

    问题分析：

    我们只需要遵循“优先使用面值大的硬币”即可。

    1、尽可能多的使用100元（即最大的）

    2、余下部分尽可能多的使用50元

    3、余下部分尽可能多的使用10元

    4、余下部分尽可能多的使用5元

    5、余下部分使用1元

    代码截图：

货币选择

参考：贪心算法秘籍 - 简书