《算法设计与分析》-第三章 动态规划

第3章动态规划（Dynamic-Programming）3.1动态规划法的基本思想3.2动态规划法的适用条件3.3动态规划法的基本步骤3.4应用举例－0/1背包问题3.1动态规划法的基本思想为求解给定问题，有一系列子问题需要解答。对这些子问题按照某种方式仔细设计，使得其后的每一个子问题都可以通过上面已经求出的一个或多个子问题的合并而获得其解。3.1动态规划法的基本思想动态规划法与分治法的异同：–与分治法类似，动态规划法也是对问题进行递归分解。–而当递归分解得到的子问题不互相独立时，用分治法求解，则有些子问题被重复计算了许多次。而动态规划法通过保存已解决的子问题的解，在需要时再找出已求得的解，可以避免大量重复计算。3.2动态规划法的适用条件动态规划法解所能解决的问题一般具有以下两个基本因素：一、最优子结构性质当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质。二、重叠子问题性质递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。其它同分治法3.2动态规划法的适用条件一、最优子结构性质当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质。例1：Fibonacci数问题nn≤1F(n)＝F(n-1)＋F(n-2)n13.2动态规划法的适用条件一、最优子结构性质当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质。例2：求解二项式系数)!(!!mnmnmnmn111mnmn11m=0n=m其它＝3.2动态规划法的适用条件一、最优子结构性质•在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。3.2动态规划法的适用条件一、最优子结构性质•例3最短路径问题设G是有向图，若G中从顶点i到顶点j有路径存在，找出最短的一条。下面证明最短路径问题具有最优子结构性质3.2动态规划法的适用条件一、最优子结构性质证明：设i,i1,i2,…,ik,j是从i到j的一条最短路径。从初始顶点i开始，设从i到下一顶点i1的判定已经做出。接下去，问题就转化为用i1替代i，重复原来的问题，找出一条从i1到j的路径。显然，i1,i2,…,ik,j一定构成了从从i1到j的最短路径（与原问题相同的最优子序列）3.2动态规划法的适用条件一、最优子结构性质证明：若不然，设i1,r1,r2,…,rp,j是一条从i1到j的最短路径，则i,i1,r1,r2,…,rp,j将是一条从i到j的路径且比路径i,i1,i2,…,ik,j要短，得出矛盾。所以，最短路径问题具有最优子结构性质。3.2动态规划法的适用条件一、最优子结构性质•利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。3.2动态规划法的适用条件二、重叠子问题性质递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。3.2动态规划法的适用条件二、重叠子问题性质例1：Fibonacci数问题的递归树Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)T(n)=O(Fib(n))3.2动态规划法的适用条件二、重叠子问题性质例2：求解二项式系数的递归树173416331733163217321632153217311631163115311531153114311631T(n)=O()mn3.3动态规划法的基本步骤找出最优解的性质，并刻划其结构特征。－－考察是否适合采用动态规划法。递归地定义最优值(建立递归式或动态规划方程)。以自底向上迭代的方式（或以自顶向下的备忘录方法）计算出最优值；根据计算最优值时得到的信息，构造最优解。3.3动态规划法的基本步骤例1Fibonacci数问题求解步骤：1具有最优子结构性质2具有重叠子问题性质3建立递归式或动态规划方程4求解值。3.3动态规划法的基本步骤intFib(intn){f1=f2=0;for(f=1,i=0;i=n;i++){f2=f1;f1=f;f=f1+f2;}returnf;}3.3动态规划法的基本步骤例2求解二项式系数求解步骤：1具有最优子结构性质2具有重叠子问题性质3建立递归式或动态规划方程4求解。3.3动态规划法的基本步骤例2求解二项式系数求解方法：1动态规划法：计算如下序列：S0={}S1={，}S2={，，}000111Sn={，，，…,}02120n221n2nnn3.3动态规划法的基本步骤例2求解二项式系数1动态规划法：0n1n2n3n4n5n6n7nPascal三角形n011112121313314146415151010516161520156171721353521713.3动态规划法的基本步骤例2求解二项式系数intBinom（intn,intm）{intb[MAXSIZE];b[0]=1;for(i=1;i=n;i++){b[i]=1for(j=i-1;j0;j++)b[j]=b[j]+b[j-1];}returnb[m];}3.3动态规划法的基本步骤例2求解二项式系数求解方法：2备忘录法：•备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。3.3动态规划法的基本步骤例2求解二项式系数2备忘录法：intBinom（intn,intm）{if(n==m||m==0){filltable(n,m,0);return1;}else{if(!lookupTable(n-1,m,t1)){t1=Binom(n-1,m);filltable(n-1,m,t1);}if(!lookupTable(n-1,m-1,t2)){t2=Binom(n-1,m-1);filltable(n-1,m-1,t2);}returnt1+t2;}}3.4应用举例－0/1背包问题0-1背包问题niiixv1maxnixCxwiniii1},1,0{1给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。3.4应用举例－0/1背包问题1最优子结构性质考查2建立递归方程3重叠子问题性质考查4求解0-1背包问题设所给0-1背包问题的子问题nikkkxvmaxnkixjxwknikkk},1,0{的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。iiiiwjwjjimvwjimjimjim0),1(}),1(),,1(max{),(nnnwjwjvjnm00),(3.4应用举例－0/1背包问题求解：1动态规划法//权为整数的迭代法思考：备忘录法0-1背包问题---权为整数的迭代法voidKnapSack(intv[],intw[],intc,intn,intm[][])//求m[][]{intjMax=min(w[n]-1,c);for(j=0;j=jMax;j++)//m(n,j)=00=jw[n]m[n][j]=0;for(j=w[n];j=c;j++)//m(n,j)=v[n]j=w[n]m[n][j]=v[n];for(i=n-1;i1;i--){intjMax=min(w[i]-1,c);for(j=0;j=jMax;j++)//m(i,j)=m(i+1,j)0=jw[i]m[i][j]=m[i+1][j];for(j=w[i];j=c;j++)//m(n,j)=v[n]j=w[n]m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c=w[1])m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]);}0-1背包问题---权为整数的迭代法voidtraceback(intm[][],intw[],intc,intx[]){//求x[]for(i=1;in;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c=c-w[i];}x[n]=(m[n][c]0?1:0);}