搜索
算法设计与分析算法设计与分析5.1贪心算法概述5.2贪心算法的理论基础5.3删数字问题5.4背包问题5.5覆盖问题5.6图的着色问题5.7遍历问题5.8最小生成树5.9哈夫曼编码算法设计与分析5.1.1贪心算法•例：求方法使生产某产品所花费的时间最少；–最直接的方法：枚举；–高效一点的方法：在生产该产品的每一道工序上都选择最省时的方法；–以逐步的局部最优，达到最终的全局最优。•贪心算法通过一系列的局部选择来得到一个问题的解。所作的每一个选择都是当前状态下“最优”的选择。•要依照某种策略。策略“只顾眼前，不管将来”，称之为“贪心策略”。•贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。5.1贪心算法概述算法设计与分析例：有一艘大船准备用来装载货物。如何在货船上装入最多的货物？已知：第i个货箱的重量为wi（1≤i≤n）；货船的最大载重量为c。这个问题可以看作是求最优解问题。求解：设xi=0；货箱i将不被装上船；xi=1；货箱i将被装上船寻找一组xi，满足条件ni=∑wixi≤c且xi∈[0,1],1≤i≤n。满足限制条件的每一组xi都是一个可行解，能使ni=∑wixi取得极大值的方案是最优解。算法设计与分析贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。如：找硬币，要找给顾客一角五分钱，硬币的面值为一分、五分、一角一分3种。贪心算法：找给顾客1个一角一分的硬币和4个一分硬币。然而3个五分硬币是最好的找法。•贪心算法能否得到最优解？算法设计与分析5.1.2.贪心算法的基本思想贪心算法的基本思想是通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足：(1)可行的：必须满足问题的约束。(2)局部最优：当前所有可能的选择中最佳的局部选择。(3)不可取消:选择一旦做出，在后面的步骤中就无法改变了。贪心算法是通过做一系列的选择来给出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择。这种启发式策略并不总是能产生出最优解。算法设计与分析例5.1删除数字问题•键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输出应包括所去掉的数字的位置和组成的新的正整数(N不超过100位)。•数据结构设计：将输入的高精度数存储为字符串格式。算法设计与分析•实例(s=3)：–n1=“12435863”•贪心策略–在位数固定的前提下，让高位的数字尽量小其值就较小；–删除高位较大的数字；–具体地相邻两位比较若高位比低位大则删除高位。•n1=“12435863”–4比3大删除4“1235863”–8比6大删除8“123563”–6比3大删除6“12353”算法设计与分析•再一个实例：–n2=“231183”–3比1大删除3“21183”–2比1大删除2“1183”–8比3大删除8“113”•由实例1，相邻数字只需要从前向后比较；而从实例2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i+1位进行比较，才能保证结果的正确性。算法设计与分析•n3=”1234567”s=3–由这个实例看出，经过对n3相邻比较一个数字都没有删除，这就要考虑将后三位进行删除；当然还有可能，在相邻比较的过程中删除的位数小于s时，也要进行相似的操作。•n4=”120083”s=3–2比0大删除2“10083”–1比0大删除1“0083”–8比3大删除8“003”算法设计与分析•由这个实例子又能看出，当删除掉一些数字后，结果的高位有可能出现数字“0”，直接输出这个数据不合理，要将结果中高位的数字“0”删除掉，再输出。特别地还要考虑若结果串是“0000”时，不能将全部“0”都删除，而要保留一个“0”最后输出。算法设计与分析#includestdio.h#includestring.hmain(){inti,j,k,m,n,x,a[200];charb[200];gets(b);for(n=0,i=0;b[i]!='\0';i++){n++;a[i]=b[i]-48;}scanf(%d,&k);i=0;m=0;x=0;while(kx&&m==0){i=i+1;if(a[i-1]a[i])/*出现递增,删除递增的首数字*/{printf(%d,a[i-1]);for(j=i-1;j=n-x-2;j++)a[j]=a[j+1];x=x+1;/*x统计删除数字的个数*/i=0;}/*从头开始查递增区间*/if(i==n-x-1)m=1;}/*已无递增区间,m=1脱离循环*/printf(\n删除后所得最大数:);for(i=1;i=n-k;i++)/*打印剩下的左边n-k个数字*/printf(%d,a[i-1]);}算法设计与分析例5.2数列极差问题在黑板上写N个正整数排成一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为M=max-min。如：对三个具体数据3，5，7讨论，可能有以下三种结果：(3*5+1)*7+1=113,(3*7+1)*5+1=111,(5*7+1)*3+1=109结论：先运算小数据得到的是最大值，先运算大数据得到的是最小值。算法设计与分析显然此问题适合用贪婪策略,不过在求最大值时，要先选择较小的数操作。求最小值时，要先选择较大的数操作。这是一道两次运用贪心策略解决的问题。1）不断从现有的数据中，选取最大和最小的两个数，计算后的结果继续参与运算，直到剩余一个数算法结束。2)选取最大和最小的两个数较高效的算法是用二分法完成，这里仅用简单的逐个比较方法来求解。注意到由于找到的两个数将不再参与其后的运算，其中一个用它们的计算结果代替，另一个用当前的最后一个数据覆盖即可。所以不但要选取最大和最小，还必须记录它们的位置，以便将其覆盖。3）求max、min过程必须独立，即求max和min都必须从原始数据开始,否则不能找到真正的max和min。算法设计与分析1)由设计2）、3）知，必须用两个数组同时存储初始数据。2)求最大和最小的两个数的函数至少要返回两个数据，方便起见用全局变量实现。ints1,s2;main(){intj,n,a[100],b[100],max,min;printf(Howmangdata?);scanf(%d,&n);printf(inputthesedata);for(j=1;j=n;j=j+1){scanf(%d,&a[j]);b[j]=a[j];}min=calculatemin(a,n);max=calculatemax(b,n);printf(max=%d,min=%d,max-min=%d,max,min,max-min);}算法设计与分析•求一组数据中两个最大值算法：a[12345678…]可以假设两个变量s1,s2分别储存这两个值所在数组中的下标，一个最大，一个次大值。数组只有两个元素时：a1a2,令s1=1,s2=2;否则s1=2,s2=1;•数组再增加一个元素j（下标）时：•if(a[j]a[s1]){s2=s1;s1=j;}•elseif(a[j]a[s2])s2=j;算法设计与分析max2(inta[],intn){intj;if(a[1]=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for(j=3;j=n;j++){if(a[j]a[s1]){s2=s1;s1=j;}elseif(a[j]a[s2])s2=j;}}intcalculatemin(inta[],intn){intj;while(n2){max2(a,n);a[s1]=a[s1]*a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]*a[2]+1);}算法设计与分析min2(inta[],intn){intj;if(a[1]=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for(j=3;j=n;j++)if(a[j]a[s1]){s2=s1;s1=j;}elseif(a[j]a[s2])s2=j;}intcalculatemax(inta[],intn){intj;while(n2){min2(a,n);a[s1]=a[s1]*a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]*a[2]+1);}算法设计与分析贪心算法例子：设计一个算法，把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为1的分数。如：7/8=1/2+1/3+1/24。基本思想：逐步选择分数所包含的最大埃及分数，这些埃及分数之和就是问题的一个解。如：7/81/2，7/8-1/21/3，7/8-1/2-1/3=1/24。过程如下：1)找最小的n（最大的埃及分数1/n），使分数f1/n；2)输出1/n；3)计算f=f-1/n；4)若此时的f是埃及分数，输出f,算法结束,否则返回1）。算法设计与分析森林里进行一场装背包比赛：•参加者：猴子黑熊啄木鸟•每个比赛者一个背包，背包的载重量为20公斤。•给定N个物品，每个物品有一定的重量和价值。20kg5.3背包问题算法设计与分析森林里进行一场装背包比赛•规则：物品可切一部分放入；背包里装的物品的总重量不超过背包的载重量；背包里装的物品的价值最高者获胜。算法设计与分析黑熊•黑瞎子掰棒子的策略：价值高的优先放入。•物品n=3，背包的载重量C=20•各个物品的价值(v1,v2,v3)=(25,24,15)•各个物品的重量(w1,w2,w3)=(18,15,10)。物品1物品212/15物品1(kg)18物品215物品224重量20价值28.2物品125物品115物品110算法设计与分析物品3物品212/3物品125物品215物品224重量20价值31物品118物品215物品310猴子•耍小聪明策略：重量小的优先放入。•物品n=3，背包的载重量C=20•各个物品的价值(v1,v2,v3)=(25,24,15)•各个物品的重量(w1,w2,w3)=(18,15,10)。算法设计与分析啄木鸟•算盘子策略：单位重量价值高的优先放入。•物品n=3，背包的载重量C=20(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10)(v1/w1,v2/w2,v3/w3)=(1.39,1.6,1.5)物品2物品311/2物品125物品315物品224重量20价值31.5物品118物品215物品310算法设计与分析•啄木鸟算盘子策略的时间复杂度?第一步:选出单位重量价值最高者装入。n个中取最大值第二步：删除该物品。第三步:重复1,2步,直至再装入就超出背包的载重量为止。第四步:把最后选择物品的一部分装入背包:剩余载重量/最后选择物品的重量O(n)O(n2)O(n)算法设计与分析啄木鸟算盘子策略•能否改进?时间复杂度?第一步:按照单位重量价值递减排序。n个数排序第二步:按排序顺序依次装入直至再装入就超出背包的载重量为止。第三步:把最后选择物品的一部分装入背包:剩余载重量/最后选择物品的重量O(nlogn)O(nlogn)O(n)算法设计与分析背包问题该问题就是背包问题：已知：给定n种物品和一个背包。物品i重量是Wi，其价值为Vi，背包容量为C。求解：如何选择装入背包的物品，使得装入背包中物品总价值最大?算法设计与分析•每个物品xi•可以不被装入背包，也可以部分装入背包,0≤xi≤1•每个物品的价值和重量值都大于0，总共有1个或者n个物品，