算法设计及分析习题

-"算法设计与分析"习题第一章算法引论1、 算法的定义？答：算法是指在解决问题时，按照*种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2、 算法的特征？答：1)算法有零个或多个输入； )算法有一个或多个输出； 3)确定性 ； )有穷性3、 算法的描述方法有几种？答：自然语言、图形、伪代码、计算机程序设计语言4、 衡量算法的优劣从哪几个方面？答：(1) 算法实现所消耗的时间时间复杂度； (2) 算法实现所所消耗的存储空间空间复杂度； (3) 算法应易于理解，易于编码，易于调试等等。5、 时间复杂度、空间复杂度定义？答：指的是算法在运行过程中所需要的资源时间、空间多少。6、时间复杂度计算： i=1； whilei<=n i=i*2； 答：语句执行次数1次，语句执行次数f(n), 2f(n)<=n,则f(n) <=log2n;算法执行时间： T(n)= 2log2n +1时间复杂度：记为O(log2n) ；7.递归算法的特点？答：每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；递归终止条件递归中用较小自变量函数值来表达较大自变量函数值；递归方程式8、算法设计中常用的算法设计谋略？答：蛮力法； 倒推法； 循环与递归； 分治法；动态规划法； 贪心法； 回溯法； 分治限界法9、设计算法：递归法：汉诺塔问题？兔子序列上楼梯问题？整数划分问题？蛮力法：百鸡百钱问题？倒推法：穿越沙漠问题？答：算法如下：（1） 递归法l 汉诺塔问题void hanoi(int n, int a, int b, int c)if (n > 0) hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a); l 兔子序列fibonaci数列 递归实现：Int F(int n) if(n<=2) return 1; else returnF(n-1)+ F(n-2);l 上楼梯问题Int F(int n) if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2);l 整数划分问题问题描述：将正整数n表示成一系列正整数之和，n=n1+n1+n3+将最大加数不大于m的划分个数，记作q(n,m)。正整数n的划分数p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系：递归算法：Int q( int n, int m)if(n<1|m<1) return 0;If(n=1)|(m=1) return 1;If (n<m) return q(n,n);If(n=m) return q(n,m-1)+1;elsereturn q(n,m-1)+q(n-m,m);（2） 蛮力法：百鸡百钱问题算法设计1：设*，y，z分别为公鸡、母鸡、小鸡的数量。 约束条件： *+y+z=100 且 5*+3*y+z/3=100main( ) int *,y,z;for(*=1;*<=20;*=*+1) for(y=1;y<=34;y=y+1) for(z=1;z<=100;z=z+1) if(100=*+y+z and 100=5*+3*y+z/3) print(the cock number is",*)； print(the hen number is", y)；print(the chick number is "z);算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低 算法设计2： 在公鸡*、母鸡y的数量确定后，小鸡的数量  z就固定为100-*-y，无需再进展枚举了 。 此时约束条件只有一个： 5*+3*y+z/3=100main( ) int *,y,z;for(*=1;*<=20;*=*+1)for(y=1;y<=33;y=y+1)z=100-*-y;if(z mod 3=0 and 5*+3*y+z/3=100)print(the cock number is",*)； print(the hen number is", y)；print(the chick number is "z); 算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断"5*+3*y+z/3=100。这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。(3) 倒推法：穿越沙漠问题desert int dis，k，oil,k; / dis表示距终点的距离，k表示贮油点从后到前的序号 dis=500;k=1;oil=500; /初始化 while ( dis<1000) print("storepoint,k,distance, 1000-dis,oilquantity,oil) /1000- dis则表示距起点的距离， k=k+1; /k表示储油点从后到前的序号 dis=dis+500/(2*k-1); oil= 500*k; print("storepoint,k,distance,dis,oilquantity,oil)； 第二章 分治算法1、分治算法根本思想是什么？ 适合用分治算法解决的问题，一般具有几个特征？ 分治算法根本步骤是什么？答：1)根本思想:将一个难以直接解决的大问题，分割成一些规模较小的一样问题，以便各个击破，分而治之。2) 特征：Ø 该问题的规模缩小到一定的程度就可以容易解决; Ø 该问题可以分解为假设干个规模较小的一样子问题，即该问题具有最优子构造性质；Ø 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。Ø 4)利用该问题分解出子问题解可以合并为该问题解; 3根本步骤： 分解、求小问题解、合并2、改写二分查找算法：设a1n是一个已经排好序的数组，改写二分查找算法:ü 当搜索元素*不在数组中时，返回小于*的最大元素位置i，和大于*的最小元素位置j； (即返回*的左、右2个元素)ü 当搜索元素*在数组中时，i和j一样，均为*在数组中的位置。并计算其时间复杂度？答：、设计一个合并排序的算法？分治法解 并计算其时间复杂度？(要求写出递推公式，及其求解过程)答：void MergeSort (int A，int low，int high) int middle; if (low<high) middle=(low+high)/2; /取中点 MergeSort(A,low,middle); MergeSort(A,middle+1,high); Merge(A,low,middle,high);/合并算法 void Merge(int A，int low，int middle，int high) /合并过程描述：int i,j,k; int *B=new inthigh-low+1;i=low; j=middle+1; k=low; while(i<=middle&&j<=high) /两个子序列非空if(Ai<=Aj) Bk+=Ai+;else Bk+=Aj+; while (i<=middle) Bk+=Ai+;/子序列Alow，middle非空，将A复制到Bwhile (j<=high) Bk+=Aj+;/子序列Amiddle+1， high非空，将A复制到Bfor(i=low;i<=high;i+) Ai+=Bi+;/将合并后的序列复制回A 合并排序算法运行时间T(n)的递归形式为：u 分析该算法时间复杂度：令T(n)为元素个数为n时所需比拟次数时间：当n=时，时间复杂度记为O(1)。当n>时，T(n)=2 T(n/2) + O(n) =2 (2T(n/22)+O(n/2) + O(n) =22T(n/22) + 2 O(n) =23T(n/23) + 3O(n) = =2* T(n/2*) + *O(n)分解到最后只有2个元素可以求解，n/2*1， *=logn; 故 T(n)=n*T(1)+n*logn ，故时间复杂度记为：On * logn、金块问题求最大最小元问题老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比拟重量的仪器，我们希望用最少的比拟次数找出最重的金块。要求：设计一算法求解该问题？ 分治法解 计算其时间复杂度？(要求写出递推公式，及其求解过程)答：递归求取最大和最小元素 ma*min int i, int j ,float &fma*, float &fminint mid; float lma*, lmin, rma*, rmin;if (i=j) fma*= ai; fmin=ai; /只有1个元素 else if (i=j-1) /只有2个元素 if(ai<aj) fma*=aj；fmin=ai; else fma*=ai; fmin=aj;else /多于2个元素 mid=(i+j)/2; ma*min i，mid，lma*，lmin;/递归调用算法求最大最小 ma*min mid+1，j，rma*，rmin;/递归调用算法求最大最小 if(lma*>rma*) fma*=lma*; /合并取大 else fma*=rma*; if(lmin>rmin) fmin=rmin; /合并取小 else fmin=lmin; u 分析该算法时间复杂度：令T(n)为元素个数为n时所需比拟次数时间：当n=2时，查找查找最大最小元只需要1次比拟，T(2)=1；时间复杂度记为O(1)。当n>2时， T(n)=2T(n/2) + 2 T(2) =4T(n/4) + 4 T(2) + 2 T(2) =8T(n/8) + 8 4 2 = =2* T(n/2*) + 2* +2*-1+8+4+2分解到最后只有2个元素可以求解，n/2*2， T(n)= 2* *1 + 2* +2*-1 + 22 + 21= 2* *1 +(2- 2*2 )/(1-2 = 2* + 2*+1 - 2 =3n/2 - 2故时间复杂度记为：On、用分治思想设计一个有效的算法，可以进展两个n位大整数的乘法运算？ 并计算其时间复杂度？要求写出递推公式，及其求解过程答：int mult( int *, int y, int n) /*, y为两个n位整数 s=sign(*)*sign(y); /s为* y的符号*=abs(*); y=abs(y); int mul;if( n=1) mul=s*y; return mul; else / 计算*Y = ac 2n + (a-b)(d-c)+ac+bd) 2n/2 + bd int a=*左边n/2位； / 移位操作，把*分为2块 int b=*右边n/2位； int c=y左边n/2位； /移位操作，把Y分为2块 int d=y右边n/2位； int m1= mult( a, c, n/2); / a, c还不够小继续分为2块,直到最后1×1位 int m2= mult( a-b, d-c, n/2); int m3= mult( b, d, n/2); mul=s*( m1*2n+(m1+m2+m3)*2n/2+m3 );return mul; 、设计一棋盘覆盖问题算法分治法？ 并计算其时间复杂度？要求写出递推公式，及其求解过程 在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。该算法中可能用到的变量：tr ：棋盘中左上角方格所在行；tc ：棋盘中左上角方格所在列。 dr： 残缺方块所在行；dl ：残缺方块所在列。size:棋盘的行数或列数；用二维数组board ，模拟棋盘。答：void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; /size:棋盘行数 int t = tile+, / L型骨牌号s = size/2; / 分割棋盘/ 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 boardtr + s - 1tc + s - 1 = t; / 用 t 号L型骨牌覆盖右下角chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖其余方格/ 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 boardtr + s - 1tc + s = t; / 用 t 号L型骨牌覆盖左下角 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖其余方格/ 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else boardtr + stc + s - 1 = t; / 用 t 号L型骨牌覆盖右上角 chessBoard(tr+s, tc, tr+s, tc+s-1, s); / 覆盖其余方格/ 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else boardtr + stc + s = t; / 用 t 号L型骨牌覆盖左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s); / 覆盖其余方格 第三章动态规划算法、动态规划算法根本思想？动态规划算法与分治算法异同点？适合用动态规划算法求解问题的根本要素？动态规划算法的根本步骤？答：1根本思想：将待求解问题分解成假设干个子问题；由于子问题有重叠，动态规划算法能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以防止大量重复计算. 2一样：都是将原问题分解成小问题，通过小问题求解得到原问题解。不同： ü 用分治法求解时,分解的子问题是互相独立的,且与原问题类型一致。分治算法实现一般用递归；ü 动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实现一般用循环; 3根本要素：具有最优子构造；子问题具有重叠性4步骤：1)分析最优解的性质，并刻划其构造特征。 2)递推地定义最优值。 3)以自底向上的方式计算出最优值.4)根据计算最优值时得到的信息，构造问题的最优解. 、序列*=*1，*2,*m 和 Y=Y1,Y2Yn的最长公共子序列为Z=Z1,Z2,Zk用动态规划的方法求序列 * 和Y的最长公共子序列长度？要求按照动态规划写出动态规划求解问题的步骤分析最优子构造写出递归方程算法描述 注：C 记录序列*与Y的最长公共子序列的长度答：最优子构造设序列*= *1，*2，*m 与 序列Y= y1，y2，yn 的一个 最长公共子序列Z= z1，z2，zk 、假设*m= yn, 则zk=*m= yn, 且 z1，z2，zk-1 是序列*m-1与 序列Yn-1的最长公共自序列；、假设*myn, 且*m zk, 则Z是*m-1与Y的最长公共子序列；、假设*myn, 且yn zk, 则Z是*与Yn-1的最长公共子序列;由此可见，2个序列的最长公共子序列包含了这2个序列的前缀去掉一个元素的最长公共子序列。 即，原问题最优解，包含子问题最优解； 因此，最长公共子序列问题具有最优子构造性质。写出递归方程循环实现，计算最优值C i j，算法描述Int lcsLength( * , y , b ) int m=*.length-1; n=y.length-1; for(int i=1; i<m;i+) Ci0=0; /y序列空 for(int i=1; i<n;i+) C0i=0; /*序列空 for (int i = 1; i <= m; i+) /*序列长为 for (int j = 1; j <= n; j+) /序列长为n if (*i=yj) Cij=Ci-1j-1+1; bij=1; else if (ci-1j>=cij-1) Cij=Ci-1j; bij=2; else Cij=Cij-1; bij=3;return Cmn;u 时间复杂度分析：该算法时间复杂度：O(m*n)构造最长公共子序列，算法描述：void LCS (char * i, Y j, int b ) if (i =0 | j=0) return; if (b i j= 1) LCS( * i-1, Y j-1, b); system.out.print( * i ); else if (b i j= 2) LCS(*i-1，Y j，b); else if (b i j= 3) LCS(* i ，Yj-1, b);u 时间复杂度分析：此算法每一次递归调用使得i或j减，因此该算法时间复杂度为O(m+n)、长江游艇俱乐部在长江上设置了n个游艇出租站1,2n.游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i，j)，其中1<=i<j<=n；试设计一个算法，计算出游艇从出租站1到出租站n所需最少租金？见习题集第三章算法设计与计算题T24、掌握动态规划方法求解背包问题？ 答：分析问题的最优解构造设y1,y2,yn所给01背包容量为M的解；则，y2,yn相应子问题背包容量为Mw1的解；即原问题最优解，包含了子问题最优解递归定义最优值计算最优值m(i，j) void knapsack( int v , int w , int M, int m )int n=v.length; if ( M<w n )/ i=n时，只有个物品 m n M=0; else if (M>=w n) m n M=v n; M=M-w n; for( int i=n-1; i>=1; i-) / i<n时，*i*n多个物品 if (M<w i) m i M=m i+1 M; else if (M>=w n) m i M=math.ma*( m i+1 M, m i+1M-w i+vi); M=M-w i; u 该算法时间复杂度：O(c*n) c常数构造最优解void trackack( int m , int w , int M, int * )/* i标记i是否放入背包 int n=w.length; for( int i=1; i<n; i+ ) /判断前n-1个物体是否放入背包 if (m i M=m i+1 M ) * i=0; else * i=1; M=M-w i; * n=(m n M>0)" 1:0 ; /判断第n个物体是否放入背包u 该算法时间复杂度：O(n) 第 4 章 贪心算法1、 贪心算法根本思想？答：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择贪心选择，最终得到整个问题的最优解2、 贪心算法的根本要素？答：贪心选择性； 最优子构造3、 贪心算法与动态规划算法的异同"答：1 一样点：对于要求解的问题都具有最优子构造；2 不同点： 算法的根本思想不同； 求解问题的类型不同；例：普通背包问题贪心算法求解0-1背包问题动态规划算法求解4、设计普通背包装载问题的贪心算法" 并分析其时间复杂度？答：float greedy_knapsack ( float M, float w , float p , float * ) / M 背包载重 * 背包问题最优解, w 物品重量， P 物品价值 int n=w.length; /n物品的个数float pp=0; /pp计算当前背包总价值float mmM; /mm背包剩余载重for( int i=1;i<=n; i+ ) float ww i= p i / w i； /计算物品单位价值ww * i=0; /初始化，所有物品没有放入背包Mergesort (w i , ww i，n ); /按单位价值将物品排序，便于贪心选择for( int i=1; i<=n; i+ ) /贪心选择，总是选择价值最大放入背包 if ( w i<=mm ) /当前物品小于背包剩余载重 * i=1; mm=mm - w i; pp=pp + p i; /整个放入背包 else * i=mm/w i; pp=pp + * i*p i; break; /i局部放入背包return pp;该算法主要包括以下几局部：Ø 计算物品单位价值时间，其时间复杂度O(n)；Ø 按照物品单位价值排序时间，其时间复杂度为O(n*logn);(合并排序时间)Ø 贪心选择时间，其时间复杂度为O(n)；故该算法的时间复杂度为：O(n*logn+2n)；记为： O(n*logn)5、设计找零问题的贪心算法" 并分析其时间复杂度？答：void greedy_zhaoling ( float GZ, int B , int S ) /GZ应发工资 B j初始化排序；/为了贪心选择，依次选最大币种 for( j=1, j<=6;j+) S j=0； /初始化S j A=GZ/B j; /A表示对应j币种数 S j=A; /S j存放对应j币种总数 GZ=GZ-A*B j; /每求出一种面额所需的数后， 一定要把这局部金额减去： for(i=1;i<=6;i+) print( B i, "-, S i); /输出币种和对应数 6、设计活动安排问题的贪心算法" 并分析其时间复杂度？答：伪代码：Int greedyselector(int s , int f , boolean a )int n=s.length; /n活动的个数；a 按活动完毕时间递增排序；/便于贪心选择a1=true; /活动被选中int j=1; /j记录最近参加活动集合A的活动j int count=1; /count存储相容活动个数for(int i=2; i<=n; i+)/贪心选择从活动j=2n判是否可参加A if( 活动i的开场时间，大于最近活动j的完毕时间 )将活动i参加活动集合A； j=i; /活动i作为最近参加活动集合A的最近活动 count+; else 活动i不参加活动集合A；return count;程序设计语言：Int greedyselector(int s , int f , boolean a )int n=s.length; /n活动的个数Mergesort (a ,f , n ); /按活动完毕时间排序，便于贪心选择a1=true; /活动被选中int j=1; /j记录最近依次参加活动集合A的活动j int count=1; /count存储相容活动个数for(int i=2; i<=n; i+) /贪心选择从活动i=2n判是否可参加A if( s i>=f j )a i=true; /将活动i参加活动集合A j=i; /活动i作为最近参加活动集合A的最近活动 count+; else a i=false; / s i<f j, 活动i不参加活动集合Areturn count;该算法主要包括局部：Ø 按照按活动完毕时间对活动排序时间，其时间复杂度为：O(n*logn)；Ø 贪心选择时间，其需要经过n-1次的比拟s i>=f j 时间复杂度为：O(n-1);故本算法的时间复杂度： O(n*lognn-1)；记为：O(n*logn)。7、掌握例dijkstra算法的求单源最短路径问题。算法设计？求解过程？答:void dijkstra (int v, float a, float dist) /v表示源,aij表示边i到j的权值 /disti记录源到顶点i的最短路径长度/previ记录顶点i的前一个点,可以找出最短路径int n=dist.length;boolean s ; /si标记顶点i是否参加顶点集合sif( v<1 | v>n) return; /源点v不存在for(int i=1;i<=n;i+) disti=avi; /初始化数组disti、si si=false; if(disti=ma*-value) /源到顶点i没有边 previ=0; else previ=v; distv=0; sv=true; /把源v参加到集合s中for(int i=1; i<n; i+)/剩下n-1个顶点，每次选择一个参加s中float tempma*-value; int u=v; for(int j=1;j<=n;j+) /贪心选择，计算V-S中顶点的dist 值，选择最小的那个顶点jif( (!sj) &&(distj<temp) ) u=j; temp=distj; su=true; /源到顶点u的最短路径已经确定，u参加到s中 for(int j=2;j<=n;j+) /根据u重新计算dist if( (!sj) &&(auj< ma*-value) /u到j有边float newdist=distu+auj;if(newdist<distj)distj=newdist; prevj=u;该算法主体有两重循环，故该算法的时间复杂度记为O(n2)8、P126图求最小生成树，写出其prim算法？并给出其选边过程"答：prim算法描述(伪代码)void prim(int n, float c)/c存储边权值 T=空集； /T表示最小生成树的边集合 S= 1 ; /S表示最小生成树包含的顶点集合 while(S!=V) 选择边i，j，iS 且j V-S；且权值cij最小；/贪心选择 T=T i，j; S=S j ； prim算法描述(程序设计语言)Void prim (int n, float c)float lowcost ; float closest ; boolean s ;s1=true;/初始化，顶点1参加生成树集合s for(int i=2;i<=n;i+) /初始化，计算与顶点1相邻顶点边权值 lowcosti=c1i; colsesti=1; si=false; for(int i=1;i<n;i+) /剩下n-1个顶点，每次选择一个参加s中 float min=float.ma*-value; int j=1;for( int k=2;k<=n; k+) /贪心选择,v-s中找使lowcost最小的顶点kif(lowcostk<min)&&(!sk) min=lowcostk; j=k; sj=true;/把找到的顶点j参加到生成树集合s中for(int k=2;k<=n; k+) /根据刚参加的顶点修改lowcost, closestif(cjk<lowcosestk)&&(!sk)lowcostk=cjk; closestk=j; 该算法主体有两重循环，故该算法的时间复杂度记为O(n2) Prim算法执行过程：首先，找出V-S中使lowcost值最小的顶点j(距离s最近的顶点j);然后，根据数组closest选取边(j,closestj)；最后，将j添加到S中，并对closest和lowcost作必要的修改。选边过程： 9、P126图，利用kruskal算法求最小生成树，给出其选边过程？答：伪代码：void krustral(int n, float c)/c存储边权值 mergesortfloat c, T; /按边权值排序 T=空集； /T表示最小生成树的边集合 while( |T|<n-1 ) /n个顶点有n-1个边选择最小权值边i，j； /贪心选择 if(iT1&&j T2)/边(i,j)一端i在T1分支,一端j在T分支 union(i,j); T=Ti，j) else T=Ti，j); 选边过程：第章 回溯算法1、回溯法根本思想？回溯法解题步骤？答：根本思想：在搜索尝试中找问题的解，当不满足条件就回溯返回，尝试别的路径。 解题步骤：(1)针对所给问题，定义问题的解空间；(2)并确定易于搜索的解空间构造(排列树，子集树);(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数，剪去无效的枝，防止无效搜索。2、什么叫子集树？什么叫排列树？ 什么叫满m叉树？答：1子集树 ：当所给问题是在n个元素的集合S中找出S满足*种性质的子集时，其相应的解空间树称作子集树。2排列树 ：当所给问题是在确定的n个元素满足*种性质的排列中搜索问题的解时，相应的解空间树被称作排列树。3满m叉树： 当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足*种性质，即寻找满足*种特性的n个元素取值的一种组合。 这类问题的解空间树称为满m叉树。3、利用回溯法，求解01背包问题，要求设计出相应算法？并分析其时间复杂度？答：算法描述递归实现double knaspack(double p , double w , double c) /c是背包载重double cw=0; /当前重量 double cp=0; /当前价值 double bestp=0; /当前最优装载价值 backtrack(1); /深度优先搜索解空间 return bestp;double backtrack( int i) /搜索解空间函数double n=p.length; if ( i>n ) / i表示深度层，i>n搜索到叶子节点 bestp=cp; return bestp; /否则，进入左子树向下深度搜索 else if (cw+w i<=c) /当前物品放入背包不超载 cw=cw+w i; cp=cp+p i; c=c-wi; backtrack(i+1); /继续向下深度搜索 else /超载，则回溯进入右子树 if ( bound(i+1)>bestp ) /通过限界函数知道右子树可能包含最优解/即，当前价值剩余物品价值大于bestp，进入右子树 backtrack( i+1 );double bound(int i) / 限界函数计算当前价值与剩余价值和 double cleft = c - cw; / 剩余容量 double b = cp; / 当前物品价值 while (i <= n && w i <= cleft) / 装载剩下的物品 cleft = cleft -w i; b= b + pi; i+; / w i> cleft 跳出循环，背包装满,物品局部装入背包 if (i <= n) b += pi/wi * cleft; return b; / 当前物品价值与剩余物品价值之和算法分析： 该算法计算上界函数bound时间复杂度为O(n); 在最坏的情况下，有2n个右孩子节点需要计算上界； 故该算法的时间复杂度为O(n*2n)4、利用回溯法，求解n后问题，要求设计出相应算法，并分析其时间复杂度？答：算法描述递归实现double nqueen(int nn) int n=nn; int sum=0; / 放置皇后的方案数 int * n; / * i表示皇后i放在棋盘的第i行，第* i列 for (int i=0;i<=n; i+;)* i=0; / 初始化 backtrack(1); / 深度优先搜索解空间 return sum; void backtrack ( int t) if( t>n ) / 搜索到叶子节点，方案数1，t是层数 sum+; else for( int i=1; i<=n; i+) / for循环一一判断皇后所在列 * t=i; / 将第t个皇后放在t行(t不同)，i列 if( place(t) ) / 约束函数，判断是否有冲突backtrack (t+1); / 放下一个皇后 void place( int k)/ 约束函数 for( int j=1;j<k; j+ ) /k之前的皇后1k-1是否与k冲突if( (math.abs(k-j)=math.abs(* k-* j) | (* k=* j) ) /k与之前的皇后1k-1不能在同一斜线或同一列 return false;else return true; 算法分析：对于n皇后问题的解空间共有n!个叶子节点，故排列树最多有n* n!个节点；最坏的情况下每个节点都要用place函数判断是否可行，每一个节点判断时间为O(n)；故该算法的时间复杂度记为O(n* n* n!) 第六章 分支限界算法1、分支限界算法的解题步骤？答：1针对所给问题，定义问题的解空间;2确定易于搜索的解空间构造(排列树，子集树);3以广度优先方式搜索问题的解空间；4)在搜索过程中用限界函数，剪去无效的枝，防止无效搜索。2、常用的两种分支限界算法？并说明其思想？答：1队列式FIFO先进先出分支限界算法将活动结点表组织成一个队列，并按照队列先进先出原则取下一个结点作为扩展结点根本思想：开场，根结点是唯一的活结点，根结点入队列；从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子(分支)，用约束条件检查限界，把所有满足约束函数的儿子结点参加活结点队列中。再从活结点表中取出队首结点队中最先进来的结点为当前扩展结点，直到找到一个解或活结点队列为空为止。2优先队列式分支限界算法将活结点表组织成一个优先队列堆，并按照优先队列中规定的结点优先级，选取优先级最高的结点作为当前扩展结点。根本思想：根结点是唯一的活结点，根结点入堆；从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子节点；用约束条件检查限界，把所有满足约束函数的儿子结点参加活结点表中堆，并给每个结点设置优先级。再从活结点表(堆)中取出堆顶结点(堆中优先级最高结点)为当前扩展结点，直到活结点表(堆)为空。3、分支限界算法与回溯法异同？答：一样点：都属于搜索算法； 都需要在问题的解空间中搜索问题的解；不同点：1求解目标不同：回溯法求解目标是找出解空间树中满足约束条件所有解；分支限界法求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在*种意义下的最优解。 2搜索方式的不同：回溯法以深度优先的方式搜索解空间树；分支限界法则以广度优先的方式搜索解空间树。4、 利用优先队列分支限界算法，设计01背包问题算法？答：队列式分支限界算法无限界函数double knaspack(double p , double w , double c)double cw=0; /当前重量 double cp=0; /当前价值 double bestp=0; /当前最优装载价值 backtrack(1); /分支限界法搜索解空间 return bestp;double backtrack( int i)while (true)/队列不空 / 检查左儿子结点 if (ew + wi <= c) enQueue(ew + wi, i); / 左儿子参加队列/进入右孩子，右儿子结点总是可行的，无上界函数enQueue(ew, i); / 右儿子参加队列 ew = (Integer) queue.remove().intValue();/ 取队首下一扩展结点 if (ew = -1)/ 同一层尾部标记ew = -1：同一层结点处理完毕 if (queue.isEmpty() return bestw;/判断队列是否为空 else queue.put(new Integer(-1); / 同层结点尾部标志 ew = (Integer)