1
第五章
贪心算法
§1贪心算法基本思想1贪心算法基本思想
找零钱假如售货员需要找给小孩67美分的零钱。现在，售货员手中只有25美分、10美分、5美分和1美分的硬币。在小孩的催促下，售货员想尽快将钱找给小孩。她的做法是：先找不大于67美分的最大硬币25美分硬币，再找不大于67－25＝42美分的最大硬币25美分硬币，再找不大于42－25＝17美分的最大硬币10美分硬币，再找不大于17－10＝7美分的最大硬币5美分硬币，最后售货员再找出两个1美分的硬币。至此，售货员共找给小孩6枚硬币。售货员的原则是拿尽可能少的硬币个数找给小孩。从另一个角度看，如果售货员将捡出的硬币逐一放在手中，最后一起交给小孩，那么售货员想使自己手中的钱数增加的尽量快些，所以每一次都尽可能地捡面额大的硬币。装载问题有一艘大船用来装载货物。假设有
个货箱，它们的体积相同，重量分别是w1w2w
，货船的最大载重量是c。目标是在船上装最多货箱该怎样装？如果用xi1表示装第i个货箱，而xi0表示不装第i个货箱，则上述问题是解优化问题：求x1x2x
，
max∑xi
i1

511
∑wixi≤c
i1


512
贪心方法，顾名思义，是在决策中总是作出在当前看来是最好的选择总是作出在当前看来是最好的选择。例贪心方法总是作出在当前看来是最好的选择如找零钱问题中，售货员每捡一个硬币都想着使自己手中的钱尽快达到需要找钱的总数。在装载问题中，每装一个货箱都想着在不超重的前提下让船装更多的箱子。但是贪心方法并未考虑整体最优解，它所作出的选择只是在某种意义上的局部最优选择。当然，在采用贪心算法时未必不希望结果是整体最优的。事实上，有相当一部分问题，采用贪心算法能够达到整体最优，如前面的找零钱问题以及后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问题等。为了更好理解贪心算法，我们将装载问题稍加推广，考虑可分割的背包问题。背包问题已知容量为M的背包和
件物品。第i件物品的重量为wi，价值是pi。因而将物品i的一部分xi放进背包即获得pixi的价值。问题是：怎样装包使所获得的价值最大。即是如下的优化问题：
f2
max
1≤i≤

∑pixi
513
1≤i≤

∑wixi≤M
0≤xi≤1pi0wi01≤i≤

514
采用贪心方法，有几种原则可循：a）每次捡最轻的物品装；b）每次捡价值最大的装；c）每次装包时既考虑物品的重量又考虑物品的价值，也就是说每次捡单位价值piwi最大的装。按原则a来装r