实验三动态规划样本

1、算法分析与设计实验报告学号姓名班级上课地点教师上课时间实验三动态规划1. 实验目的1.1理解动态规划算法的主要设计思想和基本步骤；1.2掌握用动态规划策略解决实际问题。2. 实验环境2.1 Eclipse22 Window XP3. 实验内容3.1矩阵连乘问题3.2取长公共子序列冋题3.3 0-1背包问题4.教师批改意见签字：日期：成绩实验报告细表1. 矩阵连乘问题1.1 算法设计思想(1) 分析最优解 : 计算 Ai:j 的最优次序所包含的计算矩阵子链Ai:k 和 Ak+1:j 的次序也是最优的(2)建立递归关系：设计算Ai:j, K i <j <n ,所需要的最少数乘次数 mi

2、,j, 则原问题的最优值为 m1,ni=1,2,n1pk pj当 i=j 时, Ai:j=Ai, 因此, mi,i=0,当 i<j 时, mi, j mi,k mk 1, j pi能够递归地定义 mi,j为:i mi, jmi kinjmi,k mk 1, j pi 1pk pj iikjk 的位置有 j-i 种可能( 3) 计算最优值 : 用动态规划算法解此问题 , 可依据其递归式以自底向 上的方式进行计算。 在计算过程中 , 保存已解决的子问题答案。 每个子问 题只计算一次 , 而在后面需要时只要简单查一下 , 从而避免大量的重复 计算, 最终得到多项式时间的算法public sta

3、tic void MatrixChain(int p,int m,int s) int n=p.length-1;for(int i=1;i<=n;i+)mii=0;for(int r=2;r<=n;r+)for(int i=1;i<=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi+1ij;sij=i;for(int k=i+1;k<j;k+)int t=mik+mk+1j+pi-1kj;if(t<mij)mij=t;sij=k;( 4) 构造最优解 : 算法 matrixChain 记录了构造最优解所需的全部信 息。sij=k 表明计算矩阵链

4、 Ai:j 的最佳方式在矩阵 Ak 和A+i之间断开,即最优的加括号方式为(Ai:k)(Ak+1:j)。因此, 从 s1n 记录的信息可知计算 A1:n 的最优加括号 方式为 (A1:s1n)(As1n+1:n)。而 A1:s1n 的最优加括号方式为(A1:s1s1n)(As1s1n+1:s1s1n)。同理能够确定 As1n+1:n 的最优加括号方式在 ss1n+1n 断开。照此递推下去 , 最终能够得到 A1:n 的最优完全加括号方式 , 即构造出问题的一个最优解。public static void traceback(int s,int i,int j)if(i=j)return;tra

5、ceback(s,i,sij);traceback(s,sij+1,j);System.out.println("Multiply A"+i+","+sij+"and A"+(sij+1)+","+j);1.2 程序源码矩阵连乘代码 :/* 下面是矩阵连乘问题的动态规划算法* 假设有 6 个矩阵 :* A1 A2 A3 A4 A5 A6* 30*35 35*15 15*5 5*10 10*20 20*25则 matrixChain 为* 30, 35, 15, 5, 10, 20, 25结果为* (A1 * (A2

6、 * A3) * (A4 * A5) * A6) )* author zhanlingxia*/package juzhenliancheng;public class juzhenliancheng public static void main(String args) int p = 30, 35, 15, 5, 10, 20, 25;/ 矩阵的维数存放于数组 p中matrixMultiply (p);/ 矩阵连乘public static void matrixMultiply( int p) int dimen = p. length ;int m = new int dimendi

7、men; / 定义了存放最优值数组 mint s = new int dimendimen; / 定义了记录断开位置的数组 sMatrixChain (p,m,s);System.out .println(" 最优乘法次数 : " + m1dimen - 1);System.out .println(" 划分规则为 : " );traceback (s, 1, dimen - 1);/*1: 首先计算出 mii2:然后根据递归式按矩阵链长递增的方式以此计算mii+1i=1,2,3. 。3:计算 mij 时，只要用到 mik和mk+1j*/public s

8、tatic void MatrixChain( int p, int m, int s)int n=p. length -1;for (int i=1;i<=n;i+)mii=0; / 计算单一矩阵/ 根据递归式按矩阵链长递增的方式以此计算 mii+1i=1,2,3.for (int r=2;r<=n;r+)for (int i=1;i<=n-r+1;i+)int j=i+r-1; mij=mi+1j+pi+1*pi*pj;sij=i;for (int k=i+1;k<j;k+)int t=mik+mk+1j+pi-1*pk*pj;/ 更新 mij, sij的值if (

9、t<mij)mij=t;sij=k;/按算法MatrixChain计算出断点矩阵s指示的加括号方式public static void traceback( int s, int i, int j)if (i=j) return ;traceback (s,i,sij);traceback (s,sij+1,j);System, out.pri ntln( "Multiply A" +i+"," +sij+ "andA"+(sij+1)+"," +j);1.3实验结论Hi Problems Javadoc 曉，Declaration 貝 Console 詔B< term i n a ted > J uzh e nil i a nch eng Jav 白 Application UP ogram Fi I e a vaj ire 6b injaexe (2014年冬三駆戡二基132S0Multiply A2 2and A3f 3Multiply Al,land A2t3Multiply A4j4and A5f5Multiply A4,Sand A6,&Multiply Al> 2and A4f6*1.4心得体会算法设计真的需要逻