第五章贪心算法 §1基本思想 找零钱假如售货员需要找给小孩67美分的零钱。现在,售货员 手中只有25美分、10美分、5美分和1美分的硬币。在小孩的催促 下,售货员想尽快将钱找给小孩。她的做法是:先找不大于67美分 的最大硬币25美分硬币,再找不大于67-25=42美分的最大硬币 25美分硬币,再找不大于42-25=17美分的最大硬币10美分硬币, 再找不大于17-10=7美分的最大硬币5美分硬币,最后售货员再找 出两个1美分的硬币。至此,售货员共找给小孩6枚硬币。售货员的 原则是拿尽可能少的硬币个数找给小孩。从另一个角度看,如果售货 员将捡出的硬币逐一放在手中,最后一起交给小孩,那么售货员想使 自己手中的钱数增加的尽量快些,所以每一次都尽可能地捡面额大的 硬币 装载问题有一艘大船用来装载货物。假设有n个货箱,它们的 体积相同,重量分别是W1,w2…wn,货船的最大载重量是c。目标 是在船上装最多货箱该怎样装?如果用x=1表示装第i个货箱,而 x=0表示不装第i个货箱,则上述问题是解优化问题:求x1,x2…, 满足 wx <c (5.1) 使得 max> x 1 贪心方法,顾名思义,是在决策中总是作出在当前看来是最好的
第五章 贪心算法 §1 基本思想 找零钱 假如售货员需要找给小孩 67 美分的零钱。现在，售货员 手中只有 25 美分、10 美分、5 美分和 1 美分的硬币。在小孩的催促 下，售货员想尽快将钱找给小孩。她的做法是：先找不大于 67 美分 的最大硬币 25 美分硬币，再找不大于 67－25＝42 美分的最大硬币 25 美分硬币，再找不大于 42－25＝17 美分的最大硬币 10 美分硬币， 再找不大于 17－10＝7 美分的最大硬币 5 美分硬币，最后售货员再找 出两个 1 美分的硬币。至此，售货员共找给小孩 6 枚硬币。售货员的 原则是拿尽可能少的硬币个数找给小孩。从另一个角度看，如果售货 员将捡出的硬币逐一放在手中，最后一起交给小孩，那么售货员想使 自己手中的钱数增加的尽量快些，所以每一次都尽可能地捡面额大的 硬币。 装载问题 有一艘大船用来装载货物。假设有 n 个货箱，它们的 体积相同，重量分别是w w wn , , 1 2L ，货船的最大载重量是 c。目标 是在船上装最多货箱该怎样装？如果用 = 1 i x 表示装第 i 个货箱，而 = 0 i x 表示不装第 i 个货箱，则上述问题是解优化问题：求 x1, x2,⋅⋅⋅⋅⋅⋅， xn， 满足 x c i n i ∑ i ≤ =1 w (5.1) 使得 ∑ = n i i x 1 max (5.2) 贪心方法，顾名思义，是在决策中总是作出在当前看来是最好的
选择。例如找零钱问题中,售货员每捡一个硬币都想着使自己手中的 钱尽快达到需要找钱的总数。在装载问题中,每装一个货箱都想着在 不超重的前提下让船装进更多的箱子。但是贪心方法并未考虑整体最 优解,它所作出的选择只是在某种意义上的局部最优选择。当然,在 采用贪心算法时未必不希望结果是整体最优的。事实上,有相当一部 分问题,采用贪心算法能够达到整体最优。如前面的找零钱问题以及 后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问 题等。为了更好理解贪心算法,我们将装载问题稍加推广,考虑O/1 背包问题。 0/1背包问题已知容量为M的背包和n件物品。第i件物品的 重量为w,价值是p。因而将物品i的一部分x放进背包即获得px 的价值。问题是:怎样装包使所获得的价值最大。即是如下的优化问 题 max∑px (53) ∑x1≤M l≤i≤n 0≤x1≤1,P1>0,w1>0,1≤i 采用贪心方法,有几种原则可循:a.每次捡最轻的物品装;b.每次捡 价值最大的装;c每次装包时既考虑物品的重量又考虑物品的价值 也就是说每次捡单位价值p1/w1最大的装。按原则a来装只考虑到多 装些物品,但由于单位价值未必高,总价值不能达到最大;按原则b 来装,每次选择的价值最大,但同时也可能占用了较大的空间,装的 物品少,未变能够达到总价值最大。比较合理的原则是c。事实上
选择。例如找零钱问题中，售货员每捡一个硬币都想着使自己手中的 钱尽快达到需要找钱的总数。在装载问题中，每装一个货箱都想着在 不超重的前提下让船装进更多的箱子。但是贪心方法并未考虑整体最 优解，它所作出的选择只是在某种意义上的局部最优选择。当然，在 采用贪心算法时未必不希望结果是整体最优的。事实上，有相当一部 分问题，采用贪心算法能够达到整体最优。如前面的找零钱问题以及 后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问 题等。为了更好理解贪心算法，我们将装载问题稍加推广，考虑 0/1 背包问题。 0/1 背包问题 已知容量为 M 的背包和 n 件物品。第 i 件物品的 重量为 wi，价值是 pi。因而将物品 i 的一部分 xi放进背包即获得 pixi 的价值。问题是：怎样装包使所获得的价值最大。即是如下的优化问 题： ∑ ≤i≤n i i p x 1 max (5.3) x p w i n w x M i i i i n i i ≤ ≤ > > ≤ ≤ ∑ ≤ ≤ ≤ 0 1, 0, 0, 1 1 (5.4) 采用贪心方法，有几种原则可循：a.每次捡最轻的物品装；b.每次捡 价值最大的装；c.每次装包时既考虑物品的重量又考虑物品的价值， 也就是说每次捡单位价值 i wi p 最大的装。按原则 a 来装只考虑到多 装些物品，但由于单位价值未必高，总价值不能达到最大；按原则 b 来装，每次选择的价值最大，但同时也可能占用了较大的空间，装的 物品少，未变能够达到总价值最大。比较合理的原则是 c。事实上
按照原则c来装,确实能够达到总价值最大。 0/1背包问题贪心算法 Greedy Knapsack(p,w,M,x,n)∥价值数组p[n]、重量数组w[1nl, ∥它们元素的排列顺序是p[iwi]≥p[i+1/w[t+1l,M是背包容量, ∥x是解向量 real pll: n, w[l: n), x[l n], M,rc, nteger 1, n, x=0,∥将解向量初始化为零 rc=M;∥/是背包剩余容量初始化为M for i from 1 to n do if wi> rc then exit endif x[1F1; rc=rc-w[i]; endfor if i<n then x[=rc/w[i] endif end greedy Knapsack 定理1如果p[1]/w[2]≥p[2]/w[2]≥……≥p[n/w[n],则 GreedyKnapsack对于给定的0/1背包问题实例生成一个最优解。 证明设x=(x,x2,…,xn)是 Greedy Knapsack所生成的解,但不是 最优解。因而必有某个x不为1。不妨设x是第一个这样的分量。于 是,当1≤ij时,x1=1;当jin时,x1=0;当ij时,0≤x<1
按照原则 c 来装，确实能够达到总价值最大。 0/1 背包问题贪心算法 GreedyKnapsack(p, w, M, x, n) //价值数组 p[1:n]、重量数组 w[1:n]， //它们元素的排列顺序是p[i]/w[i]≥p[i+1]/w[i+1]; M是背包容量， // x 是解向量 real p[1:n], w[1:n], x[1:n], M, rc; integer i, n; x=0; // 将解向量初始化为零 rc=M; // 是背包剩余容量初始化为 M for i from 1 to n do if w[i] > rc then exit endif x[i]=1; rc=rc-w[i]; endfor if i≤n then x[i]=rc/w[i]; endif end GreedyKnapsack 定理 1 如 果 p[1]/w[2] ≥ p[2]/w[2] ≥ ⋅⋅⋅⋅⋅⋅ ≥ p[n]/w[n], 则 GreedyKnapsack 对于给定的 0/1 背包问题实例生成一个最优解。 证明 设 x=(x1,x2,⋅⋅⋅⋅⋅⋅,xn)是 GreedyKnapsack 所生成的解，但不是 最优解。因而必有某个 xi不为 1。不妨设 xj是第一个这样的分量。于 是，当 1≤ i<j 时，xi＝1；当 j<i≤n 时，xi＝0；当 i=j 时，0≤xi<1
因为ⅹ不是最优解,则存在解向量y=(y,y,……,y,使得 ∑Py>∑Px。不妨假定∑wx=M。设k是使得y≠x的最小 下标,则y<x.这是因为:当kj时,x=1,上述不等式自然成立 当k2j时,因为x=y,x2=y2,…,xk-=y-,当k<isn时,x1=0,所 以由y>x可推出∑1y>∑x=M,y不是解向量,矛盾 现在取新的向量z=(z1,z2,…,zn)满足 Z1=y1,Z2-y2,………,Zk-1=yk-1,Zk=Xn 0≤z=≤yk,…,0≤z≤y而且∑w;(v1-z,)=wk(zk-yk) k+l≤i≤ 这样的向量z是存在的,而且是0/1背包问题的解,因为 11=∑Wy1+Wk=k∑ :2 l≤i<n l<i≤k-1 k+l≤i<n ∑y1+∑W (5.5) l≤i≤k-1 k≤i≤n ∑wy1≤M l≤i<n 至此,我们找到一个新的解向量z。以下证明它的总价值不小于y的 总价值: ∑P1=∑Py+(=k-yk)形kPk/Wk-∑(y1-)wP1/w1 l≤i<n k<isn ≥∑Py+(=k-yk)k-∑(-=)m|p4/k(5.6) k+1≤i<n ∑Py 中间的不等式是由于当Ik时有p/w≥p1/w而得。但与x的不同分量 的个数比y与x的不同分量的个数至少减少一个。以z代替y进行上 面的讨论,我们又可以找到新的解向量z,如此等等,由于分量的个
因为 x 不是最优解，则存在解向量 y=(y1,y2,⋅⋅⋅⋅⋅⋅,yn), 使 得 ∑ i i > ∑ i i p y p x 。不妨假定∑wi xi = M 。设 k 是使得 yk≠ xk的最小 下标，则 yk< xk. 这是因为：当 k<j 时，xk=1,上述不等式自然成立； 当 k≥j 时，因为 x1=y1, x2=y2,⋅⋅⋅⋅⋅⋅, xk-1= yk-1，当 k<i≤n 时，xi＝0，所 以由 yk> xk可推出∑wi yi > ∑wi xi = M ，y 不是解向量，矛盾。 现在取新的向量 z=(z1,z2,⋅⋅⋅⋅⋅⋅,zn)满足 z1=y1, z2=y2,⋅⋅⋅⋅⋅⋅, zk-1= yk-1, zk= xk 0≤zk+1≤yk+1, ⋅⋅⋅⋅⋅⋅, 0≤zn≤yn而且 ( ) ( ) 1 k k k k i n i i i ∑w y − z = w z − y + ≤ ≤ 这样的向量 z 是存在的，而且是 0/1 背包问题的解，因为 w y M w y w y w z w y w z w z i n i i k i n i i i k i i k i n k k i i i k i i i n i i = ≤ = + = + + ∑ ∑ ∑ ∑ ∑ ∑ ≤ ≤ ≤ ≤ − ≤ ≤ ≤ ≤ ≤ ≤ − + ≤ ≤ 1 1 1 1 1 1 1 (5.5) 至此，我们找到一个新的解向量 z。以下证明它的总价值不小于 y 的 总价值： ∑ ∑ ∑ ∑ ∑ ∑ ≤ ≤ ≤ ≤ + ≤ ≤ ≤ ≤ ≤ ≤ < ≤ = ≥ + − − − = + − − − i n i i k k k i n k k k i i i i n i i i i k i n k k k k k i i i i n i i i n i i p y p y z y w y z w p w p z p y z y w p w y z w p w 1 1 1 1 1 ( ) ( ) / ( ) / ( ) / (5.6) 中间的不等式是由于当 I>k 时有 pk/wk≥pi/wi而得。但与 x 的不同分量 的个数比 y 与 x 的不同分量的个数至少减少一个。以 z 代替 y 进行上 面的讨论，我们又可以找到新的解向量 z'，如此等等，由于分量的个
数n有限,必到某一步停止,我们能找到解向量y*,它和x有相同的 分量,又与y又有相同的总价值(大于x的总价值),矛盾。这个矛 盾源于ⅹ不是最优解的假设。故,x是最优解。 贪心算法主要用于处理优化问题。每个优化问题都是由目标函数 和约東条件组成。满足约束条件的解称为可行解,而那些使得目标函 数取极值的可行解称为最优解。如0/背包问题是一个优化问题,式 (53)中的函数是目标函数,而(54)式描述的要求是约束条件,这里优 化是使目标函数取最大值。贪心算法在每一步的决策中虽然没有完全 顾忌到问题整体优化,但在局部择优中是朝着整体优化的方向发展 的。为此,贪心算法首先要确定一个度量准则,每一步都是按这个准 则选取优化方案。如0/1背包问题的贪心准则是选取单位价值pw最 大物品,而装载问题的贪心算法选取的准则是选取最轻的货箱,找零 钱问题所用的贪心准则是选取面值最大的硬币。对于一个给定的问 题,初看起来,往往有若干中贪心准则可选,但在实际上,其中的多 数都不能使贪心算法达到问题的最优解。如O/1背包问题下面的实例: n=3,M=20,p=(25,24,15),w(18,15,10) 如果以价值最大为贪心准则,则贪心算法的执行过程是:首先考虑将 物品1装包,此时获得效益值25,包的剩余容量是2。然后考虑将物 品2装包,但物品2的重量15超出包的剩余容量,只能装入该种物 品的2/15,此时获得的总效益值为25+24×2/15=282。这样得到的可 行解(1,2/15,0)并不是最优解。事实上,如果以单位价值最大为 贪心准则,则贪心算法的执行过程是:先计算出各个物品的单位价值
数 n 有限，必到某一步停止，我们能找到解向量 y*,它和 x 有相同的 分量，又与 y 又有相同的总价值（大于 x 的总价值），矛盾。 这个矛 盾源于 x 不是最优解的假设。故，x 是最优解。 贪心算法主要用于处理优化问题。每个优化问题都是由目标函数 和约束条件组成。满足约束条件的解称为可行解，而那些使得目标函 数取极值的可行解称为最优解。如 0/1 背包问题是一个优化问题，式 (5.3)中的函数是目标函数，而(5.4)式描述的要求是约束条件，这里优 化是使目标函数取最大值。贪心算法在每一步的决策中虽然没有完全 顾忌到问题整体优化，但在局部择优中是朝着整体优化的方向发展 的。为此，贪心算法首先要确定一个度量准则，每一步都是按这个准 则选取优化方案。如 0/1 背包问题的贪心准则是选取单位价值 p/w 最 大物品，而装载问题的贪心算法选取的准则是选取最轻的货箱，找零 钱问题所用的贪心准则是选取面值最大的硬币。对于一个给定的问 题，初看起来，往往有若干中贪心准则可选，但在实际上，其中的多 数都不能使贪心算法达到问题的最优解。如 0/1 背包问题下面的实例： n=3, M=20, p=(25, 24, 15), w=(18,15,10) 如果以价值最大为贪心准则，则贪心算法的执行过程是：首先考虑将 物品 1 装包，此时获得效益值 25，包的剩余容量是 2。然后考虑将物 品 2 装包，但物品 2 的重量 15 超出包的剩余容量，只能装入该种物 品的 2/15，此时获得的总效益值为 25+24×2/15=28.2。这样得到的可 行解（1，2/15，0）并不是最优解。事实上，如果以单位价值最大为 贪心准则，则贪心算法的执行过程是：先计算出各个物品的单位价值