发布时间 : 星期二 文章算法设计与分析习题 - 图文更新完毕开始阅读
2）相同：都是将原问题分解成小问题，通过小问题求解得到原问题解。
不同：
? 用分治法求解时,分解的子问题是互相独立的,且与原问题类型一致。分治
算法实现一般用递归；
? 动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实
现一般用循环;
3）基本要素：具有最优子结构；子问题具有重叠性 4）步骤：1)分析最优解的性质，并刻划其结构特征。 2)递推地定义最优值。
3)以自底向上的方式计算出最优值.
4)根据计算最优值时得到的信息，构造问题的最优解.
２、序列X={X1，X2,?Xm }和 Y={Y1,Y2?Yn}的最长公共子序列为Z={Z1,Z2,?Zk} 用动态规划的方法求序列 X 和Y的最长公共子序列长度？
（要求按照动态规划写出动态规划求解问题的步骤分析①最优子结构②写出递归方程③算法描述）
注：C[ ｍ][ ｎ]记录序列X与Y的最长公共子序列的长度 答：①最优子结构
设序列X={ x1，x2，?xm } 与
序列Y={ y1，y2，?yn }的一个 最长公共子序列Z={ z1，z2，?zk }
Ⅰ、若xm= yn, 则zk=xm= yn, 且{ z1，z2，?zk-1 }是序列Xm-1与 序列Yn-1 的最长公共自序列； Ⅱ、若xm≠yn, 且xm≠ zk, 则Z是Xm-1与Y的最长公共子序列； Ⅲ、若xm≠yn, 且yn≠ zk, 则Z是X与Yn-1的最长公共子序列;
由此可见，2个序列的最长公共子序列包含了这2个序列的前缀（去掉一个元素）的最长公共子序列。 即，原问题最优解，包含子问题最优解； 因此，最长公共子序列问题具有最优子结构性质。 ②写出递归方程
③循环实现，计算最优值C[ i][ j]，算法描述 Int lcsLength( x[ ], y[ ], b[ ][ ]) { int m=x.length-1; n=y.length-1;
for(int i=1; i { C[i][j]=C[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { C[i][j]=C[i-1][j]; b[i][j]=2;} else { C[i][j]=C[i][j-1]; b[i][j]=3;} return C[m][n]; } ? 时间复杂度分析：该算法时间复杂度：O(m*n) ④构造最长公共子序列，算法描述： void LCS (char X[ i], Y[ j], int b[ ][ ]) { if (i ==0 || j==0) return; if (b[ i][ j]== 1) { LCS( X[ i-1], Y[ j-1], b); system.out.print( x[ i] ); } else if (b[ i][ j]== 2) LCS(X[i-1]，Y[ j]，b); else if (b[ i][ j]== 3) LCS(X[ i] ，Y[j-1], b); } ? 时间复杂度分析： 此算法每一次递归调用使得i或j减１，因此该算法时间复杂度为O(m+n) ３、长江游艇俱乐部在长江上设置了n个游艇出租站1,2?n. 游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。 游艇出租站i到游艇出租站j之间的租金为r(i，j)，其中1<=i （见习题集第三章算法设计与计算题T2） 4、掌握动态规划方法求解０－１背包问题？ 答：①分析问题的最优解结构 设（y1,y2,?yn）所给0－1背包容量为M的解； 则，（y2,?yn）相应子问题背包容量为M－w1的解； （即原问题最优解，包含了子问题最优解） ②递归定义最优值 ③计算最优值m(i，j) void knapsack( int v[ ], int w[ ], int M, int m[ ] [ ] ) {int n=v.length; if ( M { m[ n][ M]=v[ n]; M=M-w[ n]; } for( int i=n-1; i>=1; i--) // i m[ i] [M]=m[ i+1][ M]; else if (M>=w[ n]) { m[ i][ M]=math.max( m[ i+1][ M], m[ i+1][M-w[ i]+v[i]); M=M-w[ i]; } } } ? 该算法时间复杂度：O(c*n) c常数 ④构造最优解 void trackack( int m[ ] [ ], int w[ ], int M, int x[ ] ) {//x[ i]标记i是否放入背包 int n=w.length; for( int i=1; i { x[ i]=1; M=M-w[ i]; } } x[ n]=(m[ n][ M]>0)? 1:0 ; //判断第n个物体是否放入背包 } ? 该算法时间复杂度：O(n) 第 4 章 贪心算法 1、 贪心算法基本思想？ 答：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解 2、 贪心算法的基本要素？ 答：贪心选择性； 最优子结构 3、 贪心算法与动态规划算法的异同? 答：1 ） 相同点： 对于要求解的问题都具有最优子结构； 2 ）不同点： 算法的基本思想不同； 求解问题的类型不同； 例：普通背包问题 贪心算法求解 0-1背包问题 动态规划算法求解 4、设计普通背包装载问题的贪心算法? 并分析其时间复杂度？ 答： float greedy_knapsack ( float M, float w[ ], float p[ ], float x[ ] ) // M 背包载重 x[ ]背包问题最优解, w[ ]物品重量， P[ ]物品价值 { int n=w.length; //n物品的个数 float pp=0; //pp计算当前背包总价值 float mm＝M; //mm背包剩余载重 for( int i=1;i<=n; i++ ) { float ww[ i]= p[ i] / w[ i]； //计算物品单位价值ww[ ] x[ i]=0; } //初始化，所有物品没有放入背包 Mergesort (w[ i ], ww[ i]，n ); //按单位价值将物品排序，便于贪心选择 for( int i=1; i<=n; i++ ) //贪心选择，总是选择价值最大放入背包 { if ( w[ i]<=mm ) //当前物品小于背包剩余载重 { x[ i]=1; mm=mm - w[ i]; pp=pp + p[ i]; } //整个放入背包 else { x[ i]=mm/w[ i]; pp=pp + x[ 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[ ]按活动结束时间递增排序；//便于贪心选择 a[1]=true; //活动１被选中 int j=1; //j记录最近加入活动集合A的活动j int count=1; //count存储相容活动个数