华师大 算法设计与分析 总复习.ppt

ECNU Yinping Liu 例1. 找出伪币 16个硬币，其中1个是伪造的，且伪造硬币相对轻一些； 有一台比较两组硬币重量的仪器； 找出伪造硬币。 两两比较 分而治之：将大问题分解为小问题，分而治之 ECNU Yinping Liu 例2. 金块问题 有一袋金块，金块有轻有重； 有一台比较重量的仪器； 找出最轻和最重的金块。 传统：通过n-1次比较得到最重金块，再通过n-2次比较得到最轻的金块 分而治之：将金块分成两个袋子，分别找出两个袋子中的最轻和最重的金块，比较可得结果。可递归使用分而治之算法 (即，二分查找) ECNU Yinping Liu 例3：大整数的乘法 请设计一个有效的算法，可以进行两个n位大整数的乘法运算 小学的方法：O(n2)效率太低 分治法: a b c d X= Y= X = a 10n/2 + b // b是n/2 位十进制数 Y = c 10n/2 + d // d是n/2 位位十进制数 XY = ac 10n + (ad+bc)10n/2 + bd //4个乘法 ECNU Yinping Liu 复杂度分析 T(n)=O(n2) ?没有改进? ECNU Yinping Liu 大整数的乘法 请设计一个有效的算法，可以进行两个n位大整数的乘法运算 小学的方法：O(n2)效率太低 分治法: XY = ac10n + (ad+bc)10n/2 + bd为了降低时间复杂度，必须减少乘法的次数。 XY = ac10n + ((a-b)(d-c)+ac+bd)10n/2 + bd XY = ac10n + ((a+b)(c+d)-ac-bd)10n/2 + bd 算式中存在三个乘法 ac， bd和(a-b)(d-c) 或者ac， bd 和 (a-b)(d-c)。 ECNU Yinping Liu 复杂度分析 T(n)=O(nlog3) =O(n1.59)?较大的改进? 细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。 ECNU Yinping Liu 第四章 动 态 规 划 ECNU Yinping Liu 动态规划算法 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。 经分解得到的子问题往往不是互相独立的。在用分治法求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算。 动态规划方法采用最优原则来建立用于计算最优解的递归式。 不管前面的决策如何，此后的决策必须是基于当前状态的最优决策。 有些问题的某些递归式若不能保持最优原则，不可使用动态规划方法。 ECNU Yinping Liu 动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 ECNU Yinping Liu 应用一：0-1背包问题 设m(i, j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优解的值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下： ECNU Yinping Liu 应用一：0-1背包问题背包问题的递归函数 Int M(int i, int j) {//返回m(i,j)if(i==n)return (j w(n))? 0 : v[n];if(j w[i]) return M(i+1,j);// w[i]是物品 i 的体积return max(M(i+1,j), M(i+1,j-w[i])+v[i]); // v[i]是物品 i 的价值 } ECNU Yinping Liu 非递归算法 当 wi(1?i?n) 为正整数时，用二维数组 m[ ][ ] 存储 m[i][j]的相应值，可设计解0-1 背包问题的动态规划算法 knapsack 如下： void knapsack(int v[ ], int w[ ], int c, int m[ ][ ]) { int n=v.length-1; int jMax=min(w[n]-1,c); //进行(1)式赋值 for( int j=0; j=jMax; j++)m[n][j]=0;//当0=jw[n] for( int j=w[n]; j=c; j++) // j为背包容量m[n][j]=v[n];//当w[n] = j，m(n,j)赋值 ECNU Yinping Liu //进行(2)式赋值 for( int i=n-1;