基础-10：贪心算法

概述

在前文中解释了动态规划的基本思想，动态规划通过将一个问题划分为规模更小的有限个子问题进行求解，一般用于求解最优问题，对于每个子问题都要遍历其所有可能。如果一个问题包含若干子问题，且明确知道（或能证明推导）某个子问题一定是其解的一部分，则不用遍历所有的子问题，直接选择确定的子问题作为当前的选择，可以极大地提高算法的效率，贪心算法正是为解决此类问题而提出，典型的问题包括霍夫曼编码、小数背包问题、最少硬币数等，均可用贪心算法求解。

所谓贪心算法，就是在每一步中选择当前的最优解，本文剩余部分就用这几个例子对贪心算法的思想进行说明。

例1: 最少硬币数

假设现有1分、2分、5分、1角的硬币若干枚，给定任意一个金额m，求最少需要多少枚硬币？（注：这与前文中的求最少硬币数是不一样的）

假如有2角8分，求最少硬币数的思维是：首先选择最大面值的硬币数，需要2个1角，还剩8分；针对8分，选择当前可以选择的最大面值数，需要1个5分；以此再选择1个2分和1个1分。因此，共需要5枚硬币（注意与前文例子的不同）。这个问题对应的贪心算法程序本身非常简单，如下所示：

func LeastCoinNum(money int) int {
    tenNum := money / TEN
    money = money - tenNum*TEN

    fiveNum := money / FIVE
    money = money - fiveNum*FIVE

    twoNum := money / TWO
    oneNum := money - twoNum*TWO

    return tenNum + fiveNum + twoNum + oneNum
}

难点在于：怎么证明这个算法得到的最少硬币数。

分析：假设金额为m分，分两种情况进行讨论：

• 若m<10, 可以列出所有的最小硬币数，显然与上面的程序一致；
• 若m>=10, 假设1分、2分、5分和1角的最少硬币数分别为k₁、k₂、k₅、k₁₀, 则需要证明k₁₀=m/10是最优解。由于1角是1分、2分、5分的整数倍，假设存在另一个最少的组合中1角的数量k₁₀‘ < k₁₀且k₁₀-k₁₀' = d，则必有k₁' + k₂' + k₅' >= k₁ + k₂ + k₅ + 2d，显然，k₁'、k₂'、k₅'、k₁₀'不是最优解。（思考：前文中的最小硬币数为什么不能用贪心算法？）

利用贪心算法时，需要关注问题是否具有两个性质：

• 贪心选择性质。即通过局部最优选择可以构造全局最优解。如例1中的最小硬币数，每次都选取最大面值的硬币
• 最优子结构。即如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。（动态规划和贪心选择都具有的性质）

例1中的分析验证了这一点，但是分析过程没有严格去证明贪心选择性质和最优子结构。

例2: 霍夫曼编码

霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。

霍夫曼编码的基本思想包括：1）编码后长度尽可能小；2）能方便高效地解码。图1展示了在一段文本中字符出现的频率（只包含a-f）

图1:某段文本中a-f出现的频率、固定编码和变长编码

显然，变长编码能获得更好的效率。在霍夫曼编码中，涉及的一个重要概念是前缀码，即没有任何字符的二进制编码是其它字符二进制编码的前缀（否则，将会导致解码时非常低效，违反了霍夫曼编码的基本思想），如上图中变长编码中的abc被编码为：0.101.100=0101100.

前缀码用于简化解码过程。如果利用二叉树显示每个字符的编码形式，则更容易理解和处理，这种形式称为编码方案的二叉树。如图1示例中的定长和变长编码的两种二叉树编码形式如图2所示：

图2: 二叉树编码

最优编码方案总是对应一颗满二叉树（即不存在悬空分支的非叶子结点），（分析：假设不是满二叉树，则其中悬空的非叶子结点n，可以将n删除，用n的左孩子或右孩子替代，则n的左孩子或有孩子的编码长度将比原来少1，因此，非满二叉树得到的编码方案不是最短的，即对应的不是最优编码方案）。若存在前缀码对应的一刻满二叉树，对应字符表，对其中每个字符c，用c.freq表示c在文件中出现的次数，d_T(c)表示c在叶子结点中的深度，则编码文件需要的二进制长度为：B(T) = sum_{all c}(c.freq * d_T(c))，称B(T) 为代价。

在前缀码及对应的二叉树编码方案的基础上，霍夫曼编码就相对简单了，本文直接从算法导论中摘取相应的算法，如图3所示：

图3: 霍夫曼编码贪心算法

第1行获取文本中涉及的字符数，然后根据每个字符在文中出现的次数构造一个列表（第2行），每次从列表中挑出出现次数最低的两个字符，作为一个非叶子结点的左右孩子（第5、6、7行），然后将非叶子结点插入队列（第8行），循环n-1次，即构造完毕，最后返回编码方案（第9行）。图4更直观地显示了图1中的文本的霍夫曼编码全过程。

图4: 图1示例的编码方案

为了证明图3算法的正确性，需要对其贪心选择性质和最优子结构性质进行说明。贪心选择性质说明如下：

若C为字符表，其中每个字符c出现的次数为c.freq。令x和y是C中频率最低的两个字符，则必定存在一个最优前缀码，x和y的二进制编码长度相同，且只有最后的一位二进制不同。（符合直觉，分析也较为简单，在此不再赘述）

最优子结构的性质说明如下：

若C为字符表，其中每个字符c出现的次数为c.freq。令x和y是C中频率最低的两个字符。令C'是C去掉x和y，加入一个新字符z后得到的字母表，即C'=C-{x, y} + {z}。z.freq = x.freq + y.freq。令T'为字母表C'的任意一个最优前缀码对应的编码树。可以将T'中叶结点z替换为一个以x和y为左右孩子的内部结点，得到树T，而T是字母表C的一个最优前缀码。（对应的是算法中的5，6，7，8行，利用上文定义T(B)，结合贪心选择性质和反证法进行分析）

在贪心选择性质和最优子结构的前提下，霍夫曼编码贪心算法得到的显然是一个最优解。

例3：小数背包问题

小数背包问题是算法中非常常见的一个问题，与之对应的0-1背包问题，小数背包问题可以用贪心算法，0-1背包问题无法用贪心算法（用动态规划），下面先看小数背包问题的描述：

给定n种物品和一个背包。物品i的重量是W_i，其价值为V_i， 背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的 总价值最大? 这里，在选择物品i装入背包时，可以选择物品i的一部分， 而不一定要全部装入背包。

针对小数背包问题的说明，由于涉及众多公式编辑，并且庄老师（http://staff.ustc.edu.cn/~lszhuang/alg/ch16.pdf） 写得比我好多了，直接摘抄他的PPT，感兴趣的童鞋，可以直接查阅此PPT

小结

从概率分布的角度看，不能用贪心算法解决的问题比能用贪心算法解决的问题多得多，如在最小硬币数问题中，能否使用贪心算法取决于提供的硬币的额度之间的关系。然而，在现实中，特别是在具体问题中，很多问题都可归结为本文中提到的最小硬币数、霍夫曼编码或小数背包问题。到底是用动态规划还是用贪心算法，在具体的问题中，很多时候依赖于我们的直觉，用动态规划肯定可以得到最优解，但是有可能碰到的是一个NP问题，如列出N个元素的所有排列或组合；用贪心算法，通常可以得到一个次优解，但是不一定是最优解。如何使用，还需要各位童鞋在具体使用过程中体会。

动态规划和贪心算法，是算法中非常重要的思想，是后续稍复杂的问题的分析和处理的基础。