第四章 贪心算法

1、1第4章 贪心算法2第4章 贪心算法贪心算法总是作出在当前看来最好的选择。贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优局部最优选择。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似一定要注意，选择的贪心策略要具有无后向性。某状态以后的过程不会影响以前的状态,只与当前状态或以前的状态有关,称这种特性为无后效性。3第4章 贪心算法本章主要知识点：n4.1 哈夫曼编码n4.2 单源最短路径n4.3 最小生成树n4.4 组成最小数n4.5

2、 数列极差问题n4.6 埃及分数n4.7币种统计问题n4.8 取数游戏44.1 哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。1. 1.前缀码前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码前缀码。54.1 哈夫曼编码编码的前缀性质可以使译码方法非常简单。 表示最优前缀码最优前缀码的二叉树总是一棵完全二叉树

3、完全二叉树，即树中任一结点都有2个儿子结点。平均码长平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码最优前缀码。)()()(cdcfTBTCc 64.1 哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。 74.2 单源最短路径给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源源。现在要计算从源到所有其他各顶点的最短路长度最短路长度。这里路的长度是

4、指路上各边权之和。这个问题通常称为单源最短路径问单源最短路径问题题。1. 1.算法基本思想算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法。84.2 单源最短路径其基本思想基本思想是，设置顶点集合S并不断地作贪贪心选择心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所

5、有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。94.2 单源最短路径例如例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下页的表中。对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要 时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。)(nO)(2nO)(2nO104.2 单源最短路径迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5初始初始1-10maxint301001 11,

6、221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060DijkstraDijkstra算法的迭代过程：算法的迭代过程： 114.3 最小生成树 设G =(V,E)是无向连通带权图，即一个网络网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树最小生成树。网络的最小生成树在实际中有广泛应用。例如例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立

7、城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 124.3最小生成树1. 1.最小生成树性质最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。构造最小生成树的PrimPrim算法算法和KruskalKruskal算法算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质最小生成树性质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质

8、有时也称为MSTMST性质性质。 134.3 最小生成树2.Prim2.Prim算法算法 设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生最小生成树成树。 14例如例如，对于右图中的带权图，按PrimPrim算法算法选取边的过程如下图所示。154.3 最小生成树在上述Prim算法中，还应当考虑如何有效地找出满足条如何有效地找出满足条

9、件件i i S,jS,j V-SV-S，且权，且权cijcij最小的边最小的边(i,j)(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。 用这个办法实现的Prim算法所需的计算时间计算时间为 )(2nO164.3 最小生成树2 23 34 45 56 6S SV-SV-SCLOSESTCLOSESTLOWCOSTLOWCOST6 61 15 5112,3,4,5,

10、62,3,4,5,6CLOSESTCLOSESTLOWCOSTLOWCOST5 55 56 64 41,31,32,4,5,62,4,5,6CLOSESTCLOSESTLOWCOSTLOWCOST5 52 26 61,3,61,3,62,4,52,4,5CLOSESTCLOSESTLOWCOSTLOWCOST5 56 62,52,5CLOSESTCLOSESTLOWCOSTLOWCOST3 31,3,6,4,21,3,6,4,255CLOSESTCLOSESTLOWCOSTLOWCOST1,3,6,4,2,51,3,6,4,2,5174.3 最小生成树3.Kruskal3.Kruskal算法算

11、法Kruskal算法构造G的最小生成树的基本思想基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。 184.3最小生成树例如，例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图

12、所示。194.3 最小生成树关于集合的一些基本运算集合的一些基本运算可用于实现Kruskal算法。 按权的递增顺序查看等价于对优先队列优先队列执行removeMinremoveMin运算。可以用堆堆实现这个优先队列。 对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型并查集并查集UnionFindUnionFind所支持的基本运算。当图的边数为e时，Kruskal算法所需的计算时间计算时间是 。当 时，Kruskal算法比Prim算法差，但当 时，Kruskal算法却比Prim算法好得多。)log(eeO)(2ne)(2noe 20贪婪算法n可绝对贪婪问题, 对于输入的任何数据，贪婪

13、策略都是适用的。n组成最小数n数列极差问题n埃及分数n相近或近似贪婪问题n币种统计问题n取数游戏214.4 组成最小数n键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。n要求要求:输入数据均不需判错。输出应包括所去掉的数字的位置和组成的新的正整数（N不超过240位）。n数据结构设计：数据结构设计：对高精度正整数存储时可以考虑将输入的高精度数存储为字符串格式。根据输出要求设置数组，在删除数字时记录其位置。22问题分析在位数固定的前提下，让高位的数字尽量小其值就较小，依据此贪婪策略就可以解

14、决这个问题。总目标是删除高位较大的数字，即相邻两位比较若高位比低位大则删除高位。例（s=3） n1=“1 2 4 3 5 8 6 3”4比3大 删除 “1 2 3 5 8 6 3” 8比6大 删除 “1 2 3 5 6 3”6比3大 删除 “1 2 3 5 3”只看这个实例有可能“归纳”出不正确的算法，先看下一个实例， n2=”2 3 1 1 8 3” 3比1大 删除 “2 1 1 8 3” 2比1大 删除 “ 1 1 8 3” 8比3大 删除 “ 1 1 3”n由实例n1，相邻数字只需要从前向后比较；而从实例n2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i

15、+1位进行比较，才能保证结果的正确性。23问题分析再看以下两个实例又可总结出一些需要算法特殊处理的情况。 n3=”1 2 3 4 5 6 7” s=3 由这个实例看出，经过对n3相邻比较一个数字都没有删除，这就要考虑将后三位进行删除，当然还有可能，在相邻比较的过程中删除的位数小于s时，也要进行相似的操作。 n4=”1 2 0 0 8 3” 3比0大 删除 “1 0 0 8 3”2比0大 删除 “ 0 0 8 3”8比3大 删除 “ 0 0 3” 得到的新数数据是3 由这个实例子又能看出，当删除掉一些数字后，结果的高位有可能出现数字“0”，直接输出这个数据不合理，要将结果中高位的数字“0”全部删

16、除掉，再输出。特别地还要考虑若结果串是“0000”时，不能将全部“0”都删除，而要保留一个“0”最后输出。24问题分析1. 通过实例设计算法时，枚举的实例一定要有全面性，实例最好要能代表所有可能的情况，或者在必要时多列举几个不同的实例。2.进行算法设计时，从具体到抽象的归纳一定要选取大量不同的实例，充分了解和体会解决问题的过程、规律和各种不同情况，才能设计出正确的算法。25算法设计1算法主要由四部分组成：初始化、相邻数字比较（必要时删除）、处理比较过程中删除不够s位的情况和结果输出。 其中删除字符的实现方法很多，如：1）物理进行字符删除，就是用后面的字符覆盖已删除的字符，字符串长度改变。这样可

17、能会有比较多字符移动操作，算法效率不高。2） 可以利用数组记录字符的存在状态，元素值为“1”表示对应数字存在，元素值为“0”表示对应数字已删除。这样避免了字符的移动，字符串长度不会改变，可以省略专门记录删除数字的位置。但这样做前后数字的比较过程和最后的输出过程相对复杂一些。2） 同样还是利用数组，记录未删除字符的下标，粗略的过程如下： n=“1 2 4 3 5 8 3 3” 0 0 0 0 0 0 4比3大 删除 “1 2 3 5 8 3 3” 1 2 4 5 0 0 8比3大 删除 “1 2 3 5 3 3” 1 2 4 5 0 5比3大 删除 “1 2 3 3 3” 1 2 4 7 8这时

18、数组好象是数据库中的索引文件。此方式同样存在操作比较复杂的问题。26算法设计1n我们采用方法1）。n 一种简单的控制相邻数字比较的方法是每次从头开始，最多删除s次，也就从头比较s次。设置数组data记录删除的数字所在位置#include#includedelete(char n,int b,int k)int i; for(i=b;ilen) printf(“data error”); return;27j1=0;for (i=1;i=s ;i=i+1) for (j=1;jnj+1) /贪婪选择 delete(n,j,1); if (jj1) datai=j+i; /记录删除数字位置 els

19、e /实例2向前删除的情况实例 datai=datai-1-1; j1=j; break; if( j=length(n) break; for (i=i;i1) delete(n,1,1); /将字符串首的若干个“0”去掉 printf(“%s”,n);for (i=1;ilen) print(“data error”); return;i=0; j=1; j1=0;while(is and j=length(n)-1) while(nj=nj+1) j=j+1; if (jj1) datai=j+i; else datai=datai-1-1; i=i+1; j1=j; j=j-1; 30

20、算法设计2for (i=i;i1) delete(n,1,1); print(n);for (i=1;i=s;i=i+1) print(datai, ); 算法说明2：同算法1一样，变量i控制删除字符的个数，变量j控制相邻比较操作的下标，当删除了第j个字符后，j赋值为j-1，以保证实例2（字符串n2）出现的情况得到正确的处理。 31 在黑板上写了N个正整数作成的一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数ab+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为M=max-min。问题分析

21、： 例如：三个数据3，5，7，讨论以后可能有以下三种结果：(3*5+1)*7+1=113、(3*7+1)*5+1=111、(5*7+1)*3+1=109 由此可见，先运算小数据得到的是最大值，先运算大数据由此可见，先运算小数据得到的是最大值，先运算大数据得到的是最小值。得到的是最小值。 4.5数列极差问题32 下面再以三个数为例证明此题用贪心策略求解的合理性,不妨假设：ab=a+k10，则有以下几种组合计算结果：1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+12)(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k

22、1+k2)+1)*a+k1+13)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1 显然此问题适合用贪婪策略,不过在求最大值时，要先选择较小的数操作。反过来求最小值时，要先选择较大的数操作。这是一道两次运用贪心策略解决的问题。4.5 数列极差问题331）由以上分析，可以发现这个问题的解决方法和哈夫曼树的构造过程相似，不断从现有的数据中，选取最大和最小的两个数，计算后的结果继续参与运算，直到剩余一个数算法结束。 2) 选取最大和最小的两个数较高效的算法是用二分法完成， 这里仅仅用简单的逐个比较的方法来求解。 注意到由于找到的两个数将不再参与其后的运算

23、，其中一个自然地是用它们的计算结果代替，另一个我们用当前的最后一个数据覆盖即可。所以不但要选取最大和最小，还必须记录它们的位置，以便将其覆盖。 3）求max、min的过程必须独立，也就是说求max和min都必须从原始数据开始,否则不能找到真正的max和min。算法设计:341) 由设计2）、3）知，必须用两个数组同时存储初始数据。 2) 求最大和最小的两个数的函数至少要返回两个数据，为方便起见我们用全局变量实现。 int s1,s2; int main() int j,n,a100,b100,max,min;scanf(n);for (j=1;j2) max2(a,n); as1= as1*

24、as2+1; as2=an; n=n-1; return(a1* a2+1); max2(int a,int n) int j; if(a1=a2) s1=1; s2=2; else s1=2; s2=1; for (j=3;jas1) s2=s1; s1=j; else if (ajas2) s2=j; 36 calculatemax(int a,int n) int j; while (n2) min2(a,n); as1= as1* as2+1; as2=an; n=n-1; return(a1* a2+1); min2(int a ,int n) int j; if(a1=a2) s1

25、=1; s2=2; else s1=2; s2=1; for (j=3;j=n;j+) if (ajas1) s2=s1; s1=j; else if (aj1/2， 7/8-1/21/3， 7/8-1/2-1/3=1/24。过程如下： 1)找最小的n（也就是最大的埃及分数），使分数f1/n； 2)输出1/n； 3)计算f=f-1/n； 4)若此时的f是埃及分数，输出f,算法结束,否则返回1）。40数学模型 记真分数F=A/B；对B/A进行整除运算,商为D, 余数为0KA，它们之间的关系及导出关系如下：B=A*D+K，B/A=D+K/AD+1，A/B1/(D+1)， 记C=D+1。这样我们就找

26、到了分数F所包含的“最大的”埃及分数就是1/C。进一步计算： A/B-1/C=（A*C-B）/B*C也就是说继续要解决的是有关分子为A=A*C-B,分母为B=B*C的问题41算法设计由以上数学模型，真正的算法过程如下： 1)设某个真分数的分子为A(1），分母为B； 2)把B除以A的商的整数部分加1后的值作为埃及 分数的一个分母C; 3)输出1/C； 4)将A乘以C减去B作为新的A； 5)将B乘以C作为新的B； 6)如果A大于1且能整除B,则最后一个分母为B/A； 7)如果A1,则最后一个分母为B;否则转步骤(2).42例如：7/8=1/2+1/3+1/24的解题步骤： 同样用变量A表示分子，变

27、量B表示分母； 1.C=8+1=2 /说明7/81/2， 2.打印1/2 3.A=7*2-8=6，B=B*C=16 /在计算7/8-1/2=(7*2-8)/(7*2)=6/16=A/B4. C=16/6+1=3 /说明16/61/3， 5.打印1/3 6.A=6*3-16=2，B=B*C=16*3=48 / /在计算6/16-1/3=(6*3-16)/(16*3)=2/48=A/B 7.A1但B/A为整数24，打印1/24 结束.43算法设计int main() int a,b,c; print(“input element”); scanf(a); print(“input denomina

28、tor”); scanf(b); if(ab) print(“input error”); else if (a=1 | b %a=0) printf( a, /,b, = 1, /,b/a); else while(a!=1) c = b /a + 1 a = a * c b; b = b * c print( 1/,c); if (b % a =0 ) print (+1/; b / a); a=1; 44 某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱, 且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。请编

29、程完成。算法设计： 1) 假设从键盘输入每人的工资。 2) 对每一个人的工资，用“贪婪”的思想，先尽量多地取大面额的币种，由大面额到小面额币种逐渐统计。 3) 利用数组应用技巧,将七种币值存储在数组B。这样，七种 币值就可表示为Bi,i=1,2,3,4,5,6,7。为了能实现贪婪策略，七种币应该从大面额的币种到小面额的币种依次存储。 4) 利用数组技巧,设置一个有7个元素的累加器数组S。 4.7币种统计问题45算法算法:int main( )int main( ) int i,j,n,GZ,A int i,j,n,GZ,A； int B8=0,100,50,20,10,5,2,1,S8;int

30、 B8=0,100,50,20,10,5,2,1,S8; scanf(n); scanf(n); for(i=1;i=n;i+) for(i=1;i=n;i+) scanf(GZ); scanf(GZ); for(j=1,j=7;j+) for(j=1,j=7;j+) A=GZ/Bj; A=GZ/Bj; Sj=Sj+A; Sj=Sj+A; GZ=GZ-A GZ=GZ-A* *Bj;Bj; for(i=1;i=7;i+) for(i=1;i=7;i+) print(Bi, “-”, Si); print(Bi, “-”, Si); return 0; return 0; 算法分析算法分析: :

31、算法的时间复杂性是O（n）。 46解决问题的贪婪策略： 以上问题的背景是在我国,题目中不提示我们也知道有哪些币种,且这样的币种正好适合使用贪婪算法(感兴趣的读者可以证明 这 个 结 论 ) 。 假 若 , 某 国 的 币 种 是 这 样 的 , 共 9种:100,70,50,20,10,7,5,2,1。在这样的币值种类下,再用贪婪算法就行不通了,比如某人工资是140,按贪婪算法140=100*(1张)+20*(2张)共需要3张,而事实上,只要取2张70面额的是最佳结果,这类问题可以考虑用动态规划算法来解决。 由此，在用贪婪算法策略时，最好能用数学方法证明每一步的策略是否能保证得到最优解。 算法

32、讨论47 有2个人轮流取2n个数中的n个数，取数之和大者为胜。请编写算法，让先取数者胜，模拟取数过程。问题分析: 这个游戏一般假设取数者只能看到2n个数中两边的数,用贪婪算法的情况: 若一组数据为：6,16,27,6,12,9,2,11,6,5。用贪婪策略每次两人都取两边的数中较大的一个数,先取者胜.以A先取为例： 取数结果为： A 6,27,12,5,11=61 胜 B 16,6,9,6,2=394.8 取数游戏48 但若选另一组数据：16,27,7,12,9,2,11,6。仍都用贪婪算法，先取者A败。 取数结果为： A 16,7,9,11=43 B 27,12,6,2=47 胜 其实，若我

33、们只能看到两边的数据，则此题无论先取还是后取都无必胜的策略。这时一般的策略是用近似贪婪算法。 但若取数者能看到全部2n个数，则此问题可有一些简单的方法，有的虽不能保证所取数的和是最大，但确是一个先取者必胜的策略。4.8 取数游戏49N个数排成一行，我们给这N个数从左到右编号，依次为1，2，N，因为N为偶数，又因为是我们先取数，计算机后取数，所以一开始我们既可以取到一个奇编号的数（最左边编号为1的数）又可以取到一个偶编号的数（最右边编号为N的数）。 如果我们第一次取奇编号（编号为1）的数，则接着计算机只能取到偶编号（编号为2或N）的数； 如果我们第一次取偶编号（编号为N）的数，则接着计算机只能取

34、到奇编号（编号为1或N-1）的数； 即无论我们第一次是取奇编号的数还是取偶编号的数，接着计算机只能取到另一种编号（偶编号或奇编号）的数。数学模型50 这是对第一个回合的分析，显然对以后整个取数过程都适用。也就是说，我们能够控制让计算机自始自终只取一种编号的数。这样，我们只要比较奇编号数之和与偶编号数之和谁大，以决定最开始我们是取奇编号数还是偶编号数即可。（如果奇编号数之和与偶编号数之和同样大，我们第一次可以任意取数，因为当两者所取数和相同时，先取者为胜。4.8 取数游戏51算法设计：算法只需要分别计算一组数的奇数位和偶数位的数据之和，然后先取数者就可以确定必胜的取数方式了。以下面一排数为例：1 2 3 10 5 6 7 8 9 4奇编号数之和为25（=1+3+5+7+9），小于偶编号数之和为30（=2+10+6+8+4）。我们第一次取4，以后，计算机取哪边的数我们就取哪边的数（如果计算机取1，我们就取2；如果计算机取9，我们就取8）。这样可以保证我们自