贪心算法(greedy algorithm)
贪心算法通过做出一系列的选择来求出问题的最优解。 在每个决策点，它做出在当时看来是最佳的选择。贪心算法可以说是动态规划问题的一种特例，在学习贪心算法之前，必须先得了解动态规划算法。贪心算法总是做出局部最优的选择，并不能总能保证找到全局最优解，那我们怎么才能保证一个贪心算法能够求解一个最优化问题呢？
如果我们能够证明要解决的问题具有如下两个性质，那么我们向贪心算法迈出了重要一步。
- 贪心选择性质
最关键的要素是看问题是否具有贪心选择性质：如果我们可以通过做出局部最优选择来构造全局解。也就是说，在进行选择时，我们直接选择在当前问题看起来最优的情况，而不必考虑子问题的解。
这也是贪心算法与动态规划的不同之处，动态规划中每次的选择依赖于子问题的解，因此通常使用自底向上的方式求解动态规划问题。在贪心算法中，我们总是做出当时看起来是最佳的选择，然后求解剩下的唯一子问题。贪心算法在选择时可能依赖以前的选择，但不依赖任何将来的选择或者子问题的解。因此，动态规划算法是自底向上进行计算的，而每一个贪心算法通常时自顶向下的，进行一次又一次选择，将给定问题的实例变得更小。
- 最优子结构
如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。此性质是能否应用动态规划和贪心算法的关键要素。当应用于贪心算法时，我们可以假定，通过对原问题应用贪心选择就可以得到子问题，我们所要做的工作就是论证：将子问题的最优解与贪心选择组合在一起就能得到原始问题的最优解。
经过上述描述，我们可以按如下步骤设计贪心算法：
1.将最优化问题转化成这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
2.证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
3.证明做出贪心选择后，剩余的子问题满足性质:其最优解与贪心选择组合即可得到原问题的最优解。
问题举例：Havel-Hakimi定理
Given a list of $n$ natural numbers $d_1, d_2,…,d_n$, show how to decide in polynomial time whether there exists an undirected graph G = (V, E) whose node degrees are precisely the numbers $d_1, d_2, \cdots , d_n$. G should not contain multiple edges between the same pair of nodes, or “ loop” edges with both endpoints equal to the same node.
题目的大概意思是：给你一组数字序列，数字的大小为图的度，问这些数字的度能够构成一个图（无向无环图），如果可以，则称该序列是可图的。
怎么用贪心算法分析：
1.首先由无向图的性质分析，如果所有的度之和为奇数，显然不能构成无向图
2.如果最大的度比序列的长度还大，明显也不能构成图，因为就算所有的结点和它相连，度的值也为n-1小于n。
3.贪心选择:由非负数组成的非增序列 $s:d_1,d_2,\cdots,d_n（n>=2，d_1>=1$是可图的，当仅当序列
$$s1:d_2-1,d_3-1,\cdots d_{d_1+1}-1,d_{d1+2},\cdots,d_n$$
是可图的。序列s1中有n-1个非负数，s序列排在$d_1$之后的前$d_1$个数减1后构成s1中的前$d_1$个数。
判定过程：一直循环直到当前序列出现负数（即不是可图的情况）或者当前序列全为0 （可图）时退出。
怎么理解这个贪心选择：如果一个序列是可图的，则我们选择一个度最小的结点，然后去掉这个结点以及和这个结点相连接的边，那么剩下的结点还是可图的，当然反过来也是可以的，所以这符合贪心算法的条件，去点一个结点以及和它连接的边之后，只要判断剩下的子问题是不是可图，逐渐的减少问题的规模，直到求解。
Havel-Hakimi定理伪代码:(注意下面伪代码中的sort()排序是从大到小排序)
问题举例：霍夫曼编码(Huffman Coding)
霍夫曼编码的具体原理就不仔细介绍了，可以参考维基百科霍夫曼编码，主要在这里说说霍夫曼编码中怎么应用贪心算法。
贪心选择：构造霍夫曼树的关键之处在于每一步执行的时候，并不知道这个低频率的字符会编码为多少，只能保证它在树的最下面，使用最长的编码，这样就不会影响频率高的字符的编码。而每一步贪心的过程，都将两个频率低的字符合成一个父字符，减小了问题的规模，这样这个策略就在不影响其它字符编码的情况下，不断缩小问题的规模，直到最终求解。
参考
贪心算法如何体现在霍夫曼编码中？https://www.zhihu.com/question/22112710/answer/56030576