我们学过了基本的数据结构和算法，接下来我们学习几种更加基本的算法，贪心算法、分治算法、回溯算法、动态规划，确切的说，他们应该是算法思想，并不是具体的算法，常用来指导我们设计具体的算法和编码等。
贪心、分治、回溯、动态规划这四个算法思想，原理理解起来都不难，但是要真正掌握并且灵活应用，并不是件容易的事情。
今天我们先来学习一下贪心算法（greedy algorithm）。贪心算法有很多经典的应用，比如霍夫曼编码、Prim和Kurskal最小生成树算法、还有Dijkstra单源最短路径算法。最小生成树算法和最短路径算法我们后面再说，今天我们讲一下霍夫曼编码，看看它是如何利用贪心算法来实现对数据压缩编码，有效节省数据存储空间的。
关于贪心算法，我们先看一个例子。
假设我们有一个可以容纳100kg物品的背包，可以装各种物品。我们有以下5种豆子，每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装那些豆子？每种豆子又该装多少呢？
| 物品 | 重量（kg） | 总价值(元) |
|---|---|---|
| 黄豆 | 100 | 100 |
| 绿豆 | 30 | 90 |
| 红豆 | 60 | 120 |
| 黑豆 | 20 | 80 |
| 青豆 | 50 | 75 |
实际上，这个问题很简单，我估计你一下子就能想出来，没错，我们只要先算一算每个物品的单价，按照单价由高到低依次来装就行了。单价从高到低排列，顺序依次是：黑豆、绿豆、红豆、青豆、黄豆，所以，我们可以往背包里装20kg黑豆，30kg绿豆、50kg红豆。
这个问题的解决方法显而易见，它本质上借助的就是贪心算法。结合这个问题，我们来总结一下贪心算法的解决步骤。
第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
类比到刚刚的例子，限制值就是重量不能超过100kg，期望值就是物品的总价值。这组数据就是5种豆子。我们从中选出一部分，满足重量不超过100kg，并且总价值最大。
第二步，我们尝试看下这个问题是否能用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
类比到刚才的例子，我们每次都从剩下的豆子里面，选择单价最高的，也就是重量相同的情况下，对价值贡献最大的豆子。
第三步，我们举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下，举几个例子验证一下就可以了，严格的证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。而且，从实践的角度看，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。
实际上，用贪心算法解决问题的思路，并不总能给出最优解。
我举一个例子，在一个有权图中，我们从顶点S开始，找一条到顶点T的最短路径（路径中边的权值和最小）。贪心算法的解决思路是，每次都选择一条跟当前顶点相连的权最小的边，知道找到顶点T。按照这种思路，我们求出的最短路径是S–A–E–T，路径长度是1+4+4=9.
但是这种贪心的选择方式，最终求的路径并不是最短路径，因为路径S–B–D–T才是最短路径，因为这条路径上的长度是2+2+2=6.为什么贪心算法在这个问题上不工作了呢？
在这个问题上，贪心算法不工作的主要原因是，前面的选择，会影响到后面的选择。如果我们第一步从顶点S走到顶点A，那接下来面对的顶点和边，跟第一步从顶点S走到顶点B，是完全不同的。随意即便我们第一步选择最优的走法，但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。
对于贪心算法，你是不是还有点懵？如果死抠理论的话，很难啊理解透彻。掌握贪心算法的关键是多练习，只要多练习几道题，自然就有感觉了。
1、分糖果
我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m < n），所以糖果只能分给一部分孩子。
每个糖果的大小不等，这m个糖果的大小分别是s1，s2,s3,s4……sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子对糖果大小的需求的时候，孩子才得到满足，假设这n个孩子对糖果大小的需求分别是g1,g2,g3,g4……gn。
我的问题是，如何分配糖果，能尽可能满足最多数量的孩子。
我们可以把这个问题抽象成，从n个孩子中，抽取一部分孩子分配糖果，让满足的孩子的个数（期望值）是最大的。这个问题的限制值就是糖果的个数m。
我们现在来看如何利用贪心算法来解决。对于一个孩子来说，如果小的糖果可以满足，我们就没必要用更大的糖果，这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面，我们可以从需求小的孩子开始分配糖果，因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们贡献的期望值是一样的。
我们每次从剩下的孩子中，找出对糖果大小需求最小的孩子，然后发给他剩下的糖果能满足他的需求的最小的糖果。这样的分配方案，就是满足孩子个数最多的方案。
2、钱币找零
这个问题在我们生活中更加普遍。假设我们有1元、2元、5元、10元、20元、50元、100元这些面额的纸币，他们的张数分别是c1、c2、c5、c10、c20、c50、c100.我们现在要用这些钱来支付k元，最少要用到多少张纸币呢？
在生活中，我们一般会先用面额最大的来支付，就继续用面额更小一点的，以此类推，最后用1元补齐。
在贡献相同期望值（纸币数目）的情况下，我们希望多贡献点金额，这样就可以让纸币更少，这就是一种贪心算法的解决思路。直觉告诉我们，这种处理方法就是最好的，实际上，要更严谨的证明这种贪心算法的正确性，需要比较复杂、有技巧的数学推倒，不建议花太多的时间在上main，不过如果你感兴趣的话，可以自己研究下。
3、区间覆盖
假设我们有n个区间，区间的起始端点和结束端点分别是[l1, r1],[l2, r2], [l3, r3]……, [ln, rn]。我们从这n个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间？
这个问题的处理思路稍微不是那么好懂，不过，我建议你最好能弄懂，因为这个处理思想在很多贪心算法问题中都有用到，比如任务调度、教师排课等。
这个问题的解决思路是这样的：我们假设区间中最左端点是lmin，最右端点是lmax。这个问题就相当于，我们选择几个不相交的区间，从左向右将[lmin， lmax]覆盖上。我们按照起始端点从小到大的顺序对这n个区间排序。
我们每次选择的时候，左端点跟前面的已经覆盖的区间不重合，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间
经过上面的几个例子，相信你已经对贪心算法有了一个大致的了解，现在来看看开篇的问题，如何用贪心算法实现霍夫曼编码？
假设我有1000个字符串的文件，每个字符占1个byte，存储这1000个字符就需要8000bits，那有没有更加节省空间的存储方式呢？
假设我们通过统计分析发现，这1000个字符中只包含6种不通的字符。假设他们分别是a、b、c、d、e、f。而三个二进制位bit就可以标识8个不同的字符，所以，为了尽量减少存储空间，每个字符我们用3个二进制位来表示。那存储1000个字符只需要3000bit就可以了，比原来的存储方式节省了很多空间。不过还有没有更加节省空间的存储方式呢？
霍夫曼编码就要登场了。霍夫曼编码是一种十分有效的编码方法，广泛应用于数据压缩中，其压缩率通常在20%-90%之间。
霍夫曼编码不仅会考察文本中有多少个不同的字符，还会考察每个字符出现的频率，根据频率的不同，选择不同的编码，霍夫曼编码试图用不等长的编码方法，来进一步增加压缩的效率。如果给不同频率的字符选择不同长度的编码呢？根据贪心的思想，我么可以把出现频率比较多的字符，用稍微短一些的编码，出现频率较少的字符，用稍微长一点的编码。
对于等长的编码来说，我们解压缩起来很简单。比如刚才呢那个例子中，我们用3个bit表示一个字符。在解压缩的时候，我们每次从文本中读取3位二进制码，然后翻译成对应的字符。但是，霍夫曼编码是不等长的，每次应该读取1位还是2位、3位来解压缩呢？这个问题就导致霍夫曼编码解压缩起来比较复杂。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。
｜｜