练习
1. 证明找零钱问题（例1 3 - 4）的贪婪算法总能产生具有最少硬币数的零钱。
2. 考虑例1 3 - 4的找零钱问题，假设售货员只有有限的2 5美分， 1 0美分，
5美分和1美分的硬币，给出一种找零钱的贪婪算法。这种方法总能找出具有最少硬币数的零钱吗？证明结论。
3. 扩充例1 3 - 4的算法，假定售货员除硬币外还有50, 20, 10, 5, 和1美元的纸币，顾客买价格为x 美元和y
美分的商品时所付的款为u 美元和v 美分。算法总能找出具有最少纸币与硬币数目的零钱吗？证明结论。
4. 编写一个C + +程序实现例1 3 - 4的找零钱算法。假设售货员具有面值为1 0 0，2 0，1
0，5和1美元的纸币和各种硬币。程序可包括输入模块（即输入所买商品的价格及顾客所付的钱数），输出模块（输出零钱的数目及要找的各种货币的数目）和计算模块（计算怎样给出零钱）。 5. 假设某个国家所使用硬币的币值为1 4 , 2 , 5和1分，则例1 3 - 4的贪婪算法总能产生具有最少硬币数的零钱吗？证明结论。 6. 1) 证明例1 3 - 5的贪婪算法总能找到最优任务分配方案。
2) 实现这种算法，使其复杂性为O (nl o gn)（提示：根据完成时间建立最小堆）。
*7. 考察例1 3 -
5的机器调度问题。假定仅有一台机器可用，那么将选择最大数量的任务在这台机器上执行。例如，所选择的最大任务集合为{a,b,e}。解决这种任务选择问题的贪婪算法可按步骤选择任务，每步选择一个任务，其贪婪准则如下：从剩下的任务中选择具有最小的完成时间且不会与现有任务重叠的任务。
1) 证明上述贪婪算法能够获得最优选择。
2) 实现该算法，其复杂性应为O(nl o gn)。（提示：采用一个完成时间的最小堆）
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-27 19:39:26
b
等级：职业侠客 文章：470 积分：956
门派：黑客帝国
注册：2003-8-28
第 4 楼
1.3 应用
1.3.1 货箱装船
这个问题来自例1 -
2。船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。
例1-7 假设n =8, [w1 , ... w8 ]=[100,200,50,90,150,50,20,80], c= 4 0 0。利用贪婪算法时，所考察货箱的顺序为7 , 3 , 6 , 8 , 4 , 1 , 5 , 2。货箱7 , 3 , 6 , 8 ,
4 , 1的总重量为3 9 0个单位且已被装载，剩下的装载能力为1 0个单位，小于剩下的任何一个货箱。在这种贪婪解决算法中得到[x1
, ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且åxi = 6。 定理1-1 利用贪婪算法能产生最佳装载。
证明可以采用如下方式来证明贪婪算法的最优性：令x = [x1 , ..., xn ]为用贪婪算法获得的解，令y =[ y1 , ..., yn ]为任意一个可行解，只需证明n åi= 1xi ≥n åi= 1yi 。不失一般性，可以假设货箱都排好了序：即wi≤wi + 1（1≤i≤n）。然后分几步将y
转化为x，转换过程中每一步都产生一个可行的新y，且n åi = 1yi 大于等于未转化前的值，最后便可证明n åi = 1xi ≥n åj = 1yi 。
根据贪婪算法的工作过程，可知在[0, n] 的范围内有一个k，使得xi =1, i≤k且xi =0, i>k。寻找[ 1
,n]范围内最小的整数j，使得xj≠yj 。若没有这样的j 存在，则n åi= 1xi =n åi = 1yi 。如果有这样的j
存在，则j≤k，否则y 就不是一个可行解，因为xj≠yj ，xj = 1且yj = 0。令yj = 1，若结果得到的y
不是可行解，则在[ j+ 1 ,n]范围内必有一个l 使得yl = 1。令yl = 0，
由于wj≤wl ，则得到的y
是可行的。而且，得到的新y 至少与原来的y 具有相同数目的1。
经过数次这种转化，可将y 转化为x。由于每次转化产生的新y 至少与前一个y 具有相同数目的1，因此x 至少与初始的y
具有相同的数目1。货箱装载算法的C + +代码实现见程序1 3 - 1。由于贪婪算法按货箱重量递增的顺序装载，程序1 3 -
1首先利用间接寻址排序函数I n d i r e c t S o r t对货箱重量进行排序（见3 .
5节间接寻址的定义），随后货箱便可按重量递增的顺序装载。由于间接寻址排序所需的时间为O (nl o gn)（也可利用9 . 5 .
1节的堆排序及第2章的归并排序），算法其余部分所需时间为O (n)，因此程序1 3 - 1的总的复杂性为O (nl o gn)。 程序13-1 货箱装船 template
void ContainerLoading(int x[], T w[], T c, int n) {// 货箱装船问题的贪婪算法
// x[i] = 1 当且仅当货箱i被装载， 1<=i<=n // c是船的容量, w 是货箱的重量 // 对重量按间接寻址方式排序 // t 是间接寻址表
int *t = new int [n+1];
I n d i r e c t S o r t ( w, t, n); // 此时, w[t[i]] <= w[t[i+1]], 1<=i for (int i = 1; i <= n; i++) x[i] = 0; // 按重量次序选择物品 for (i = 1; i <= n && w[t[i]] <= c; i++) { x[t[i]] = 1; c -= w[t[i]];} // 剩余容量 delete [] t; } ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:39:39 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 5 楼 1.3.2 0/1背包问题 在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n åi=1pi xi 取得最大值。约束条件为n åi =1wi xi≤c 和xiÎ[ 0 , 1 ] ( 1≤i≤n)。 在这个表达式中，需求出xt 的值。xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。 例1-8 在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n 种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi 。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。这个问题可仿照0 / 1背包问题进行建模，其中车对应于背包，货物对应于物品。 0 / 1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。 另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。 还可以利用另一方案，价值密度pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可 装入包的pi /wi 值最大的物品，这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。 我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧， 0 / 1背包问题是一个N P-复杂问题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。虽然按pi /wi 非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数时候能很好地接近最后算法。在6 0 0个随机产生的背包问题中，用这种启发式贪婪算法来解有2 3 9题为最优解。有5 8 3个例子与最优解相差1 0 %，所有6 0 0个答案与最优解之差全在2 5 %以内。该算法能在O (nl o gn)时间内获得如此好的性能。我们也许会问，是否存在一个x (x<1 0 0 )，使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点，考虑例子n =2, w = [ 1 ,y], p= [ 1 0 , 9y], 和c= y。贪婪算法结果为x=[1,0], 这种方案的值为1 0。对于y≥1 0 / 9，最优解的值为9 y。因此，贪婪算法的值与最优解的差对最优解的比例为( ( 9y - 1 0)/9y* 1 0 0 ) %，对于大的y，这个值趋近于1 0 0 %。但是可以建立贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优值的x% (x<100) 之内。首先将最多k 件物品放入背包，如果这k 件物品重量大于c，则放弃它。否则，剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序装入。通过考虑由启发法产生的解法中最多为k 件物品的所有可能的子集来得到最优解。 例13-9 考虑n =4, w=[2,4,6,7], p=[6,10,12,13], c = 11。当k= 0时，背包按物品价值密度非递减顺序装入，首先将物品1放入背包，然后是物品2，背包剩下的容量为5个单元，剩下的物品没有一个合适的，因此解为x = [ 1 , 1 , 0 , 0 ]。此解获得的价值为1 6。 现在考虑k = 1时的贪婪启发法。最初的子集为{ 1 } , { 2 } , { 3 } , { 4 }。子集{ 1 } , { 2 }产生与k= 0时相同的结果，考虑子集{ 3 }，置x3 为1。此时还剩5个单位的容量，按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1，它适合，因此取x1 为1，这时仅剩下3个单位容量了，且剩余物品没有能够加入背包中的物品。通过子集{ 3 }开始求解得结果为x = [ 1 , 0 , 1 , 0 ]，获得的价值为1 8。若从子集{ 4 }开始，产生的解为x = [ 1 , 0 , 0 , 1 ]，获得的价值为1 9。考虑子集大小为0和1时获得的最优解为[ 1 , 0 , 0 , 1 ]。这个解是通过k= 1的贪婪启发式算法得到的。 若k= 2，除了考虑k< 2的子集，还必需考虑子集{ 1 , 2 } , { 1 , 3 } ,