深入浅出贪心算法

前言

到目前为止学了数组、链表两类物理数据结构，和栈、队列两类线性逻辑结构，以及树（二叉树、二叉查找树、红黑树）、图非线性数据结构，以及基于这些数据结构的二分查找、DFS/BFS、递归、排序等算法。

接下来会学习贪心、分治、回溯、动态规划这 4 个算法思想，这类算法思想都有原理容易理解，但是很难掌握和灵活应用的特点。

一，如何理解贪心算法

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心算法解决问题的步骤：

第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。

第二步，我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。

第三步，我们举几个例子看下贪心算法产生的结果是否是最优的。

二，贪心算法实例

1，分糖果

有 m 个糖果和 n 个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m<n)。

所以糖果只能分配给一部分孩子。每个糖果的大小不等，这 m 个糖果的大小分别是 s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。

假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。如何分配糖果，能尽可能满足最多数量的孩子？

2，钱币找零

这个问题在我们的日常生活中更加普遍。假设我们有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付 K 元，最少要用多少张纸币呢？

3，区间覆盖

假设我们有 n 个区间，区间的起始端点和结束端点分别是 $[l_1, r_1]，[l_2, r_2]，[l_3, r_3]，……，[l_n, r_n]$。我们从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？

参考资料

《数据结构与算法之美》