之前的课程中,我们学习了运用贪心算法解决问题的两个例子:最少纸币问题和埃及分数问题。在进一步学习用贪心算法解决问题的技巧之前,我们先做一个小结。
贪心算法逐步构建问题的解决方案,总是选择能直接带来当前最大利益的步骤。
贪心算法可以用于解决优化类的问题,特别是当该问题具有如下的特征:在每一步都选择当前看起来的最佳选择,并且最后能得到整个问题的最优解决方案。
如果一个贪心算法可以解决某个问题,通常它也是解决该问题的最佳方案,因为贪心算法通常比其他算法,例如动态规划(Dynamic Programming,DP)算法,更加高效。
但是贪心算法并不能适用所有优化问题的场合。
例如它可以用于解决分数背包问题(Fractional Knapsack),但是它不适用于0-1背包问题(0-1 Knapsack)。
0-1背包问题:我们有一堆物品S={a1,a2,...,an},每一个物品ai都有对应的重量wi和价值vi。现在有一个背包,这个背包的容量为W,现在要将选择物品放入背包,所选物品的总重量不能超出背包容量,并使得背包里面物品的价值最大。注意:物品不能只选取其中一部分,必须选择整个(1),或者不选(0)!
分数背包问题:这个问题和上面的问题相似,唯一不同的就是该问题里可以对物品可以进行分割,即可以只选取一个物品ai的一部分放入背包。
用贪心算法解决分数背包问题,采取的策略是“每次从剩余的物品中选择Vi/Wi 比值最大的物品放入背包”,它总能找到最优解。但是对于0-1分数背包问题,贪心算法不能保证找到最优解。
我们来看一个例子。
假设我们有三个物品a1,a2,a3以及一个容量W为50的背包,这三个物品{重量,价值}分别为:a1 {w1=10,v1=60}、a2 {w2=20,v2=100}以及a3 {w3=30,v3=120}。
我们对每个物品计算价值与重量的比值:v1/w1=6,v2/w2=5,v3/w3=4。
采用贪心算法,首先选择比值最高(也就是单位重量价值最高)的a1放入背包,然后再放入a2,因为此时a3不能全部放入背包,于是我们把a3进行切割,把它的一部分放入背包。请看下图。
为什么我们不能用贪心算法来解决0-1背包问题呢?
我们还是按照之前的将平均价值最大的放入背包里面,放入a1,然后再加入a2,此时已经不能再把a3整体放入了,此时得到背包物品总价值为60+100=160。
但这明显不是最优解!随便举一个反例就可以证明:只放入a2和a3,就可以使总价值达到100+120=220。
下面列出了一些运用贪心算法解决问题的非常有名的例子:
Kruskal的最小生成树(MST):在Kruskal的算法中,我们通过逐步挑选边来创建MST,贪心选择策略是选择迄今为止构造的MST中不会导致循环的具有最小权重的边。
Prim的最小生成树:在Prim的算法中,我们通过逐步挑选边来创建MST。我们维护两组集合:一组已经包含在MST中的顶点和一组尚未包括的顶点。贪心选择策略是选择连接两组集合的具有最小权重的边。
Dijkstra的最短路径:Dijkstra的算法与Prim的算法非常相似。最短路径树是通过逐步选择边构建的。我们维护两组集合:一组已包含在树中的顶点和一组尚未包括的顶点。贪心选择策略是选择连接两个集合的边,并且它属于从源点到包含尚未包含的顶点的集合的最小权重路径上。
霍夫曼编码:霍夫曼编码是一种无损压缩技术。它为不同的字符分配可变长度的位代码。贪心选择策略是将具有最小比特长度代码分配给最常见的字符。
现在我们给出一个贪心算法的课后练习题:
问题:给你n个活动的开始时间和结束时间,从中选择你可以参与的活动,但是同一时间你只能参与一个活动,请找出你可以参与的最多活动数。
例如:考虑下面3个活动a1,a2和a3, 它们{开始时间点,结束时间点}分别为:
a1 {start=10,finish=20}
a2 {start=12,finish=25}
a3 {start=20,finish=30}
这种情形下,一个人最多只能参与2个活动:a1和a3,它们开始的时间点分别为10和20。
请你设计一种贪心算法解决下面的类似问题:考虑下面6个活动,请找出你可以参与的最多活动数
a1 {start=0,finish=6}
a2 {start=1,finish=2}
a3 {start=3,finish=4}
a4 {start=5,finish=7}
a5 {start=5,finish=9}
a6 {start=8,finish=9}
我们下一课将对活动选择问题进行详细讲解。
联系客服