贪心算法示例

简单

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

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

（发现这题还是稍微证一下好一点）

\[设所求分数为 \frac{n}{m}=\frac{n}{kn-b}, 0<b<n\\ \frac{n}{kn-b}=\frac{n-b/k+b/k}{kn-b}=\frac{1}{k}+\frac{b/k}{kn-b}\\ \therefore k=\lceil\frac{kn-b}{n}\rceil=\lceil \frac{m}{n} \rceil\]

Huffman Code 哈夫曼编码

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

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

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

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

选出两个频率最低的字符，连到一个父结点，并其频率相加作为父结点的频率，然后从原字符表中删除这两个字符，并将父结点添加进去
重复步骤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)$

上篇贪心算法

下篇回溯算法