贪心算法示例

简单

下面是一些简单问题,仅给出代码。

Egyptian Fraction 古埃及分数

问题描述 我们将分子为 $1$,分母为正整数得分数称为“单位分数”。任意真分数都可以表示成若干个不同的单位分数之和,比如:$2/3=1/2+1/6$。请用贪心算法将任意真分数拆分成单位分数之和。

Python代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#Python3 program to print a fraction  
#in Egyptian Form using Greedy 
#Algorithm 
  
#import math package to use 
#ceiling function 
import math 
  
#define a function egyptianFraction  
#which receive parameter nr as 
#numerator(分子) and dr as denominator(分母)
def egyptianFraction(nr, dr): 
  
    print("The Egyptian Fraction " +
          "Representation of {0}/{1} is". 
                format(nr, dr), end="\n") 
  
    # empty list ef to store 
    # denominator 
    ef = [] 
  
    # while loop runs until  
    # fraction becomes 0 i.e, 
    # numerator becomes 0 
    while nr != 0: 
  
        # taking ceiling 
        x = math.ceil(dr / nr) 
  
        # storing value in ef list 
        ef.append(x) 
  
        # updating new nr and dr 
        nr = x * nr - dr 
        dr = dr * x 
  
    # printing the values 
    for i in range(len(ef)): 
        if i != len(ef) - 1: 
            print(" 1/{0} +" .  
                    format(ef[i]), end = " ") 
        else: 
            print(" 1/{0}" . 
                    format(ef[i]), end = " ") 
  
#calling the function 
egyptianFraction(6, 14) 
  
#This code is contributed  
#by Anubhav Raj Singh 

(发现这题还是稍微证一下好一点)

Huffman Code 哈夫曼编码

问题描述 一个文本文件中出现了 $n$ 个字符:$c_1,\cdots,c_n$,对应出现的频率为 $f(c)$。现在要用 0,1 对每个字符编码,问如何编码才能使文本文件最小?

问题分析 用一个二叉树来表示编码,我们规定二叉树左边的边代表0,右边的边代表1,字符放在叶子节点,每个叶子节点对应得编码就是从根到叶子所经过的边。

显然,频率越高的边,编码越短;频率越低的边,编码越长。我们将频率乘编码长之和称为平均码长: $B(Tree)=\sum_{c} f(c)d(c)$

Huffman 提出了一种编码,可以使二叉树平均码长达到最优。方法如下:

  1. 选出两个频率最低的字符,连到一个父结点,并其频率相加作为父结点的频率,然后从原字符表中删除这两个字符,并将父结点添加进去
  2. 重复步骤1. 直到所有字符都在二叉树中

要证明这个贪心算法正确性,只需要证这个问题满足

  • 贪心选择性质:如果$x,y$ 是 $C$ 中频率最小的两个字符,则其编码只有最后一位不同。可以先假设 $x,y$ 不在同一层,然后可以通过对调使得 $x,y$ 在同一层,并且平均码长减小。
  • 最优子结构性质:证明如果将 $x,y$ 的父结点 $z$ 看做一个字符,则形成的子二叉树依然是最优,即:$T-{x,y}$ 依然是 $(C-{x,y})\cup {z}$ 的最优二叉树。可以假设子树不是最优,然后推导出原树也不是最优,从而与前提矛盾。

最小生成树

问题描述 给一个无向图 $G=(V,E)$,$V$ 是点集合,$E$ 是边集合。从中选取多条边,将所有节点连接成一个树,并且要求边的权重和最小。

问题分析

显然这个满足最优子结构,因为子树依然是子图的最小权重树。贪心选择性质也同样满足,假如最后形成了两个树,则我们需要选择这两个树之间最小的边,这样最终的树才是最小的。

我们最先想到的方法就是从权重最小的边开始,一条一条试,如果形成了环,就删除,反之就加入到树。通过贪心选择性质可以证明这样形成的树是最小的。这种方法称为 Kruskal 算法。这个算法的复杂度与边数有关

另一个方法叫 Prim 算法:先从一个点开始,将点周围权重最小的边和节点加入树,然后考虑这个树周围的边,再将周围权重最小的边和节点加入树,如此往复,即可得到最小权重树。同样是通过贪心选择性质证明。由于 Prim 算法每次加入边需要遍历 $n$ 个点,而需要加入 $n$ 个点,所以复杂度为 $O(n^2)$