贪心算法 & 哈夫曼编码

从一个例子说起

有100kg的物品背包，5种以下的豆子，让背包中所装物品价值最大，如何选择在背包中装哪些豆子？每种豆子又该装多少呢？

这里我们先计算每一种物品的单位重量的价值，即

单价高到低依次是：黑豆(4)、绿豆(3)、红豆(2)、青豆(1.5)、黄豆(1)。
很容易得到答案是：20kg黑豆+30kg绿豆+50kg红豆，总价值204+303+50*2 = 270

贪心算法：针对一组数据，定义了限制值(100kg)和期望值(装入背包的总价值)，希望选出几个数据，在满足限制值的情况下，期望值最大。

注：实际上用贪心算法解决问题的思路，并不总是能给出全局最优解（局部最优解）

在一个有权图中，我们从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。贪心的思路是每次选择一条和当前顶点相连的权最小的边，直到找到顶点T，按照这个思路找到的最短路径是S->A->E->T， 长度 1+4+4 = 9，而最短路径是S->A->E->T， 2+2+2 = 6

哈夫曼/霍夫曼编码

哈夫曼编码目的是编码过程中减少体积。
以编码一段字符串为例，哈夫曼编码是一种不定长的编码，不仅会考察文本多少个不同的字符，还会对每个字符出现的频率不同，选择不同长度的编码（出现的频率越高，所用的编码越短），来达到压缩的效率。

但是由于哈夫曼编码不等长，每次读取几位来确定解压就变的复杂，为了避免这一点，哈夫曼编码要求各个字符的编码不会出现某个编码是另一个的前缀（哈夫曼树的作用），这样解压缩的，读取尽可能长的可解压的二进制串，这样也不会有歧义。

我们把每个字符看作一个节点，并且附带着把频率放到优先级队列中。我们从队列中取出频率最小的两个节点 A、B，然后新建一个节点 C，把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点。最后再把 C 节点放入到优先级队列中。重复这个过程，直到队列中没有数据。（这里用到了贪心）

然后给每个边画一个权值，左边子节点的标记为0，右边的标记为1，根结点到叶节点对应的字符就是哈夫曼编码