理解贪心算法
贪心算法是一种算法思想,并不是一个具体的算法,因此我们用两个例子来理解什么样的问题适合用贪心算法解决。
例一
现在有一个能装 100g 物品的背包,和一些可拆分的物品(见表格),怎么装才能使背包中物品价值最大?
物品
重量
价值
A
100g
100
B
60g
120
C
50g
150
D
20g
50
容易想到的方法是通过计算物品单价,从高到低往背包中放。
例二
在一个加权有向图中,求 A 到 G 的最短距离。
若依旧使用例一中的方法,则找到的路径是 A->B>D>E>G,明显不是最短的路径。
综述
例一和例二的相同点:
要得到最终的结果,都需要多次决策,
比如例一中每次决策选择一个物品,例二中每次决策选择一条路。
例一和例二的区别:
例一中每次决策都不会影响后续的决策范围,即选择了一个物品后,下次选择范围仍然是所有物品,而例二中,第一次决策选择一条路后,第二次决策的可选项会受到第一次决策的影响。
假设我们给例一增加条件:物品 B 和 D 不能在背包中共存,如此,贪心算法便不可用了,因为当我们在某次决策中选择了物品 B 后,会影响到下一次决策。
贪心算法,就是在每一次决策时,都选择当前最优的选项。
贪心算法练习
钱币找零问题。
人民币有 1 元,5 元,10 元,20 元,50 元,100 元面值的钱,当我们要找零 98 元时,如何凑呢?
通常做法是从面值大的开始凑,即 1 张 50,2 张 20,1 张 5,4 张 1,可以得到 98。
区间覆盖问题
现在有几个区间[6,8],[2,4],[3,5],[1,5],[5,9],[8,0],要求的是两两不相交的区间最多有几个?
解决思路,首先对这些区间排序,以右边值从小到大排序,右边值相同的情况下,按左边值从小到大排序,决策时,候选区间左端点不能与已选择的区间相交。
哈夫曼编码
假设现在有 10000 个字符,均是由a,b,c,d,e,f,g这7个字符构成,每个字符占 8 bit,一共需要占 80000 bit,思考如何压缩呢?
方法一:7 个字符可以使用 3 bit 来表示,因为 3 bit 可以表示 8 个字符
000,001,010,011,100,101,110,111,每个字符用 3 位表示,总大小为 30000 bit。
方法二:哈弗曼编码,统计 10000 个字符中,a,b,c,d,e,f,g的出现频率,频率高的编码少,频率低的编码多。
每个字符的编码都不等长的话,在解码的时候,为了避免出现歧义,字符的编码不能存在前缀关系。
计算哈夫曼编码一般是使用一个优先队列,将每个字符看做一个节点,节点的值是字符的出现频次,每次从队列中取两个节点,组合成一个节点,再入队。
字符
出现的频率
编码
a
45
0
b
13
101
c
12
100
d
16
110
e
9
1111
f
5
1110
以上述方法画出哈夫曼树: