1、第第3章章 动态规划（动态规划（Dynamic-Programming）l3.1 动态规划法的基本思想l3.2 动态规划法的适用条件l3.3 动态规划法的基本步骤l3.4 应用举例0/1背包问题3.1 动态规划法的基本思想动态规划法的基本思想l为求解给定问题，有一系列子问题需要解答。对这些子问题按照某种方式仔细设计，使得其后的每一个子问题都可以通过上面已经求出的一个或多个子问题的合并而获得其解。3.1 动态规划法的基本思想动态规划法的基本思想l动态规划法与分治法的异同：与分治法类似，动态规划法也是对问题进行递归分解。而当递归分解得到的子问题不互相独立时，用分治法求解，则有些子问题被重复计算了许
2、多次。而动态规划法通过保存已解决的子问题的解，在需要时再找出已求得的解，可以避免大量重复计算。3.2 动态规划法的适用条件动态规划法的适用条件l一、最优子结构性质当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质最优子结构性质。l二、重叠子问题性质递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子子问题的重叠性质问题的重叠性质。l其它同分治法3.2 动态规划法的适用条件动态规划法的适用条件一、最优子结构性质当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质最优子结构性质。例1：Fibonacci数问题 n n1 F(n)
3、F(n-1)F(n-2)n13.2 动态规划法的适用条件动态规划法的适用条件一、最优子结构性质当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质最优子结构性质。例2：求解二项式系数)!(!mnmnmnmn111mnmn11m=0n=m其它3.2 动态规划法的适用条件动态规划法的适用条件一、最优子结构性质在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。3.2 动态规划法的适用条件动态规划法的适用条件一、最优子结构性质例3 最短路径问题设G是有向图，若G中从
4、顶点i到顶点j有路径存在，找出最短的一条。下面证明最短路径问题具有最优子结构性质3.2 动态规划法的适用条件动态规划法的适用条件一、最优子结构性质l证明：l 设i,i1,i2,ik,j是从i到j的一条最短路径。从初始顶点i开始，设从i到下一顶点i1的判定已经做出。接下去，问题就转化为用i1替代i，重复原来的问题，找出一条从i1到j的路径。显然，i1,i2,ik,j一定构成了从从i1到j的最短路径（与原问题相同的最优子序列）3.2 动态规划法的适用条件动态规划法的适用条件一、最优子结构性质l证明：若不然，设i1,r1,r2,rp,j是一条从i1 到j的最短路径，则i,i1,r1,r2,rp,j将
5、是一条从i到j的路径且比路径i,i1,i2,ik,j要短，得出矛盾。所以，最短路径问题具有最优子结构性质。3.2 动态规划法的适用条件动态规划法的适用条件一、最优子结构性质利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。3.2 动态规划法的适用条件动态规划法的适用条件二、重叠子问题性质递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子子问题的重叠性质问题的重叠性质。3.2 动态规划法的适用条件动态规划法的适用条件二、重叠子问题性质例1：Fibonacci数问题的递归
6、树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：求解二项式系数的递归树173416331733163217321632153217311631163115311531153114311631T(n)=O()mn3.3 动态规划法的基本步骤动态规划法的基本步骤l找出最优解的性质，并刻划其结构特征。考察是否适合采用动态规划法。l递归地定义最优值(建立递归式或动态规划方程)。l以自底向上迭代的方式（或以自顶向下的备忘录方法）计算出最优值；l根
7、据计算最优值时得到的信息，构造最优解。3.3 动态规划法的基本步骤动态规划法的基本步骤l例1 Fibonacci数问题求解步骤：1 具有最优子结构性质2 具有重叠子问题性质3 建立递归式或动态规划方程4 求解值。3.3 动态规划法的基本步骤动态规划法的基本步骤int Fib(int n)f1=f2=0;for(f=1,i=0;i=n;i+)f2=f1;f1=f;f=f1+f2;return f;3.3 动态规划法的基本步骤动态规划法的基本步骤l例2 求解二项式系数求解步骤：1 具有最优子结构性质2 具有重叠子问题性质3 建立递归式或动态规划方程4 求解。3.3 动态规划法的基本步骤动态规划法的
8、基本步骤l例2 求解二项式系数求解方法：1 动态规划法：计算如下序列：S0=S1=，S2=，000111Sn=，,02120n221n2nnn3.3 动态规划法的基本步骤动态规划法的基本步骤l例2 求解二项式系数 1 动态规划法：0n1n2n3n4n5n6n7nPascal 三角形n0 11 1 12 1 2 1 3 1 3 3 14 1 4 6 4 15 1 5 10 10 5 1 6 1 6 15 20 15 6 17 1 7 21 35 35 21 7 13.3 动态规划法的基本步骤动态规划法的基本步骤l例2 求解二项式系数int Binom（int n,int m）int bMAXSI
9、ZE;b0=1;for(i=1;i0;j+)bj=bj+bj-1;return bm;3.3 动态规划法的基本步骤动态规划法的基本步骤l例2 求解二项式系数求解方法：2 备忘录法：备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。3.3 动态规划法的基本步骤动态规划法的基本步骤l例2 求解二项式系数2 备忘录法：int Binom（int n,int m）if(n=m|m=0)filltable(n,m,0);return 1;elseif(!lookupTable(n-1,m,t1)t1=Binom(
10、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);return t1+t2;3.4 应用举例应用举例0/1背包问题背包问题niiixv1maxnixCxwiniii1,1,01给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。3.4 应用举例应用举例0/1背包问题背包问题设所给0-1背包问题的子问题nikkkxvmaxnkixjxwkni
11、kkk,1,0的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。iiiiwjwjjimvwjimjimjim0),1(),1(),1(max),(nnnwjwjvjnm00),(3.4 应用举例应用举例0/1背包问题背包问题void KnapSack(int v,int w,int c,int n,int m )/求m int jMax=min(wn-1,c);for(j=0;j=jMax;j+)/m(n,j)=0 0=jwn mnj=0;for(j=wn;j=wn mnj=vn;for(i=n-1;i1;i-)int jMax=min(wi-1,c);for(j=0;j=jMax;j+)/m(i,j)=m(i+1,j)0=jwi mij=mi+1j;for(j=wi;j=wn mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c;if(c=w1)m1c=max(m2c,m2c-w1+v1);void traceback(int m,int w,int c,int x)/求x for(i=1;i0?1:0);
