动态规划算法和实例分析.pptVIP

动态规划算法和实例分析 动态规划简介 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=jw(i)时，物品i不可能装入，最大效益值与m(i+1,j)相同； 当j=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=c;j++) //计算m(n,j) if(j=w[n]) m[n][j]=p[n]; else m[n][j]=0; 0-1背包问题 逆推动态规划算法设计 最优值计算 ⑵逆推计算m(i,j) for(i=n-1;i=1;i--) //逆推计算m(i,j),i=n-1...1 for(j=0;j=c;j++) if(j=w[i]m[i+1][j]m[i+1][j-w[i]]+p[i]) m[i][j]=m[i+1][j-w[i]]+p[i]; else m[i][j]=m[i+1][j]; ⑶经过上述推导，最优值在m[1][c]中。 最优值推导示例 0-1背包问题 逆推动态规划算法设计 构造最优解—步骤1 if 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;i=n-1;i++) if(m[i][cw]m[i+1][cw]) //x(i)=1,装载w(i) { cw-=w[i]; //cw=cw-x(i)*w(i) sw+=w[i]; sp+=p[i]; printf(%2d\t%3d\t%3d\n,i,w[i],p[i]); } 0-1背包问题 逆推动态规划算法设计 构造最优解—步骤2 比较所装载的物品效益之和与最优值，决定w(n)是否装载，方法： if (m[1][c]-效益之和) 等于 物品n的效益p[n] 装入w(n) if(m[1][c]-sp=