第8讲+动态规划算法和实例分析ppt课件.ppt
动态规划算法和实例分析,动态规划简介0-1背包问题最长公共子序列,动态规划简介,动态规划的基本思想 动态规划(DP：Dynamic Programming)是一种重要的程序设计手段，其基本思想是在对一个问题的多阶段决策中，按照某一顺序，根据每一步所选决策的不同，会引起状态的转移，最后会在变化的状态中获取到一个决策序列。 动态规划就是为了使获取的决策序列在某种条件下达到最优。动态规划是一种将多阶段决策过程转化为一系列单阶段问题，然后逐个求解的程序设技方法。引例：已知6种物品和一个可载重量为60的背包，物品i(i=1,2,6)的重量wi分别为(15,17,20,12,9,14)，产生的效益pi分别为(32,37,46,26,21,30)。装包时每一件物品可以装入，也可以不装，但不可拆开装。确定如何装包，使所得装包总效益最大。,动态规划简介,动态规划的基本思想引例分析多阶段决策问题，装每一件物品就是一个阶段，每个阶段都有一个决策：物品装还是不装。约束条件和目标函数按照单位效益最大化装包，得xi的序列为(0,1,1,1,1,0)，总效益为130按重量最大化装包，得xi的序列为(0,1,1,0,1,1)，总效益为134结论：决策序列(0,1,1,0,1,1)为最优决策序列,动态规划简介,动态规划的步骤将所求最优化问题分成若干个阶段，找出最优解的性质，并刻画其结构特征。将问题发展到各个阶段时所处的不同状态表示出来，确定各个阶段状态之间的递推关系，并确定初始(边界)条件。应用递推求解最优值。根据计算最有值时所得到的信息，构造最优解。动态规划问题的特征最优子结构。问题的最优解包含了其子问题的最优解，则称该问题具有最优子结构性质。重叠子问题。用递归算法自顶向下解问题时，有些子问题会被反复计算多次，称这些字问题重叠。动态规划算法利用这种子问题重叠性质，对每个字问题只解一次(保存下来)，已有尽可能多的利用这些子问题的解。,动态规划算法和实例分析,动态规划简介0-1背包问题最长公共子序列,0-1背包问题,0-1背包问题,逆推动态规划算法设计建立递推关系设m(i,j)为背包容量j，可取物品范围为i,i+1,n的最大效益值。则当0=w(i)时，有两种选择：不装入物品i，这时的最大效益值与m(i+1,j)相同；装入物品i，这时会产生效益p(i)，背包剩余容量为j-w(i)，可以选择物品i+1,n来装，最大效益值为m(i+1,j-w(i)+p(i)；,0-1背包问题,0-1背包问题,逆推动态规划算法设计最优值计算,根据边界条件计算m(n,j)for(j=0;j=wn) mnj=pn; else mnj=0;,0-1背包问题,逆推动态规划算法设计最优值计算,逆推计算m(i,j) for(i=n-1;i=1;i-) /逆推计算m(i,j),i=n-1.1 for(j=0;j=wi经过上述推导，最优值在m1c中。,最优值推导示例,0-1背包问题,逆推动态规划算法设计构造最优解步骤1if m(i,cw) m(i+1,cw), i=1,2,n-1 则x(i)=1，装载w(i); 其中：cw从c开始(cw=c)，cw=cw-x(i)*w(i)else x(i)=0，不装载w(i);,cw=c;for(sp=0,sw=0,i=1;imi+1cw) /x(i)=1,装载w(i) cw-=wi; /cw=cw-x(i)*w(i) sw+=wi; sp+=pi; printf(%2dt%3dt%3dn,i,wi,pi); ,0-1背包问题,逆推动态规划算法设计构造最优解步骤2比较所装载的物品效益之和与最优值，决定w(n)是否装载，方法： if (m1c-效益之和) 等于 物品n的效益pn 装入w(n),if(m1c-sp=pn)/判断w(n)是否装载 sw+=wi; sp+=pi; printf(%2dt%3dt%3dn,n,wn,pn);,knapsack(0-1),动态规划算法和实例分析,动态规划简介0-1背包问题最长公共子序列,最长公共子序列,最长公共子序列概念子序列一个给定序列的子序列是在该序列中删去若干元素后所得到的序列。即：给定X=x1,x2,xm和Z=z1,z2,zk，X的子序列是指存在一个严格递增下标序列i1,i2,ik，使得对于所有的j=1,2,k，有zj=xij。例如：Z=b,d,c,a是X=a,b,c,d,c,b,a的一个子序列公共子序列若序列Z是序列X的子序列，又是序列Y的子序列，则称Z是序列X和序列Y的公共子序列。例如：序列bcba是abcbdab与bdcaba的公共子序列,最长公共子序列,问题描述给定两个序列X=x1,x2,xm和Y=y1,y2,yn，找出序列X和Y的最长公共子序列。,最长公共子序列,最长公共子序列,最长公共子序列,逆推动态规划算法设计计算最优值,根据边界条件计算c(i,n)和c(m,j)m=strlen(x); n=strlen(y);for(i=0;i=m;i+) cin=0; for(j=0;j=n;j+) cmj=0;,最长公共子序列,逆推动态规划算法设计计算最优值,逆推计算c(i,j) for(i=m-1;i=0;i-) for(j=n-1;j=0;j-) if(xi=yj) cij=ci+1j+1+1; else if(cij+1ci+1j) cij=cij+1; else cij=ci+1j; 经过上述推导，最优值在c00中。,最优值推导示例,最长公共子序列,逆推动态规划算法设计构造最优解为了能够构造最优解，在逆推计算最优值的过程中，利用s(i,j)记录x(i)与y(j)比较的结果：当x(i)=y(j)时， s(i,j)=1当x(i)!=y(j)时，s(i,j)=0X序列的每一项与Y序列的每一项逐一比较，根据s(i,j)与c(i,j)的取值构造最长公共子序列。对x(i)与y(j)比较，其中i=0,1,m-1; j=t,n-1(t从0开始），当确定最长公共子序列中的一项时，通过t=t+1操作避免重复取项。若s(i,j)=1且c(i,j)=c(0,0)时，取x(i)为最长公共序列中的第1项。若s(i,j)=1且c(i,j)=c(0,0)-w时，取x(i)为最长公共序列中的第w项（其中，w从0开始，每确定最长公共子序列中的一项，w增一）。,最长公共子序列,逆推动态规划算法设计构造最优解,for(t=0,w=0,i=0;i=m-1;i+) for(j=t;j=n-1;j+) if(sij=1 ,CommonSubsequence,
