1
实验六 贪心算法设计技术的应用
一、算法设计技术
贪心策略是指从问题的初始状态出发,通过若干次的贪心选择而得出最优值
(或较优解)的一种解题方法。
例 1:找零钱,一个小孩买了价值少于 1 美元的糖,并将 1 美元的钱交给售
货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为 25
分、10 美分、5 美分、及 1 美分的硬币。售货员分步骤组成要找的零钱数,每次
加入一个硬币。选择硬币时所采用的贪心策略如下:每一次选择应使零钱数尽量
增大。为保证解法的可行性(即:所给的零钱等于要找的零钱数),所选择的硬
币不应使零钱总数超过最终所需的数目。
假设需要找给小孩 67 美分,首先入选的是两枚 25 美分的硬币,第三枚入选
的不能是 25 美分的硬币,否则硬币的选择将不可行(零钱总数超过 67 美分),
第三枚应选择 10 美分的硬币,然后是 5 美分的,最后加入两个 1 美分的硬币。
其实,从“贪心策略”一词我们便可以看出,贪心策略总是做出在当前看来
是最优的选择,也就是说贪心策略并不是从整体上加以考虑,它所做出的选择只
是在某种意义上的局部最优解,而许多问题自身的特性决定了该题运用贪心策略
可以得到最优解或较优解。可以证明采用上述贪心算法找零钱时所用的硬币数目
的确最少。
利用贪心策略解题,必须考虑两个问题,首先,问题是否适合于用贪心策略
求解;其次,是在确定了可以用贪心策略之后,如何选择一个贪心标准,才能保
证得到问题的最优解。
例 2:背包问题。现有载重为 M 公斤的背包和 n 种货物。第 i 种货物的重量
为 Wi,它的总价值为 Pi,假定 M、Wi、Pi 均为整数。采用怎样的装货方法,才
能使装入背包的货物总价值达到最大?
【分析】当货物总重量∑Wi 小于或等于 M 时,把所有货物装入,总价值就达
到最大。因此,关键是解决当总重量大于 M 时装货的方法。
我们先从一个具体例子入手来研究一下本题的特点。
设 n=3;M=20。
W1=15 W2=10 W3=8
P1=18 P2=15 P3=10
有几种可能解(设 Xi 为第 i 种货物所取的重量):
X1 X2 X3 总重∑Xi 总价值∑PiXi/Wi
(1) 10 5 5 20 25.75
(2) 10 10 0 20 27
(3) 2 10 8 20 27.4
(4) 4 0 16 20 22.4
显然第 3 个解总价值最大。
上述可能解是采用穷举方法试探所得众多可能解中的 4 种,这在具体的程序
编制和实现过程中相当麻烦,且在时间复杂度上很难承受,是否可以寻找到一种
简单而又时间效率高的方法呢?
下面用贪心策略来解此题。首先应该确定贪心的量度标准。一种设想是按价
值大小作为标准,先放价值最大的货物,再放价值次大的货物。即按价值从大到