实验三动态规划

　 算法 分析 与 设计 实验报告

　 学号

　姓名

　班级

　上课地点

　教师

　上课时间

　实验 三

　动态规划 1. 实验目的 1.1 理解动态规划算法的主要设计思想和基本步骤； 1.2 掌握用动态规划策略解决实际问题。

　2. 实验环境 2.1 Eclipse 2.2 Window XP 3. 实验内容 3.1 矩阵连乘问题 3.2 最长公共子序列问题 3.3 0-1 背包问题

　4. 教师批改意见

　 签字：

　日期：

　成绩

　 实验报告细表 1 1. . 矩阵连乘问题

　 1.1

　算法设计思想

　(1) 分析最优解：计算 A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的

　(2)建立递归关系：设计算 A[i:j]，1≤i≤j≤n，所需要的最少数乘次数 m[i,j]，则原问题的最优值为 m[1,n]

　当 i=j 时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n 当 i<j 时，j k ip p p j k m k i m j i m1] , 1 [ ] , [ ] , [   

　可以递归地定义 m[i,j]为：

　    j i p p p j k m k i mj ij i mj k i} ] , 1 [ ] , [ { min0] , [1j k i k 的位置有 j-i 种可能 （3）计算最优值：用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法 public static void MatrixChain(int []p,int [][]m,int [][]s) {

　 int n=p.length-1;

　for(int i=1;i<=n;i++)m[i][i]=0;

　for(int r=2;r<=n;r++)

　 for(int i=1;i<=n-r+1;i++)

　 {

　 int j=i+r-1;

　 m[i][j]=m[i+1][j]+p[i+1][i][j];

　 s[i][j]=i;

　 for(int k=i+1;k<j;k++)

　 {

　int t=m[i][k]+m[k+1][j]+p[i-1][k][j];

　if(t<m[i][j]){

　 m[i][j]=t;

　 s[i][j]=k;

　}

　 }

　 } }

　（4）构造最优解：算法 matrixChain 记录了构造最优解所需的全部信息。

　s[i][j]=k 表明计算矩阵链 A[i:j]的最佳方式在矩阵 A k 和

　A k+1 之间断开，即最优的加括号方式为(A[i:k])(A[k+1:j])。

　因此，从 s[1][n]记录的信息可知计算 A[1:n]的最优加括号

　方式为 (A[1:s[1][n]])(A[s[1][n]+1:n])。而 A[1:s[1][n]]的最

　优加括号方式为 (A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]])。

　同理可以确定 A[s[1][n]+1:n]的最优加括号方式在 s[s[1][n]+1][n]处断开。

　照此递推下去，最终可以得到 A[1:n]的最优完全加括号方式，

　即构造出问题的一个最优解。

　public static void traceback(int [][]s,int i,int j) {

　if(i==j)return;

　traceback(s,i,s[i][j]);

　traceback(s,s[i][j]+1,j);

　System.out.println("Multiply A"+i+","+s[i][j]+"and A"+(s[i][j]+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 * 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[dimen][dimen];

　//定义了存放最优值数组m

　 int[][]s = new int[dimen][dimen];

　//定义了记录断开位置的数组s

　MatrixChain (p,m,s);

　System. out .println("最优乘法次数：" + m[1][dimen - 1]);

　 System. out .println("划分规则为：");

　 traceback (s, 1, dimen - 1);

　 }

　/*1：首先计算出m[i][i]

　 2：然后根据递归式按矩阵链长递增的方式以此计算m[i][i+1]i=1,2,3.。。。

　 3：计算m[i][j]时，只要用到m[i][k]和m[k+1][j]*/ public static void MatrixChain( int []p, int [][]m, int [][]s) {

　int n=p.length-1;

　for( int i=1;i<=n;i++)m[i][i]=0;//计算单一矩阵

　//根据递归式按矩阵链长递增的方式以此计算m[i][i+1]i=1,2,3.。。。

　for( int r=2;r<=n;r++)

　 for( int i=1;i<=n-r+1;i++)

　 {

　 int j=i+r-1;

　 m[i][j]=m[i+1][j]+p[i+1]*p[i]*p[j];

　 s[i][j]=i;

　 for( int k=i+1;k<j;k++)

　 {

　 int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

　//更新m[i][j]，s[i][j]的值

　f if(t<m[i][j])

　{

　 m[i][j]=t;

　 s[i][j]=k;

　}

　 }

　 } } // 按算法MatrixChain计算出断点矩阵s指示的加括号方式

　public static void traceback( int [][]s, int i, int j)

　{

　 f if(i==j) return;

　 traceback (s,i,s[i][j]);

　 traceback (s,s[i][j]+1,j);

　 System. out .println("Multiply A"+i+","+s[i][j]+"and A"+(s[i][j]+1)+","+j);

　} }

　1.3

　实验结论

　 4 1.4 心得体会 算法设计真的需要逻辑思维，能得到结果挺开心的。

　: 2: 最长公共子序列

　2.1 算法设计思想 (1)

　设 序 列 X={x 1 ,x 2 ,…,x m } 和 Y={y 1 ,y 2 ,…,y n } 的 最 长 公 共 子 序 列 为Z={z 1 ,z 2 ,…,z k } ，则 若 x m =y n ，则 z k =x m =y n ，且 Z k-1 是 X m-1 和 Y n-1 的最长公共子序列。

　若 x m ≠y n 且 z k ≠x m ，则 Z 是 X m-1 和 Y 的最长公共子序列。

　若 x m ≠y n 且 z k ≠y n ，则 Z 是 X 和 Y n-1 的最长公共子序列

　(2)建立递归关系：由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用 c[i][j]记录序列和的最长公共子序列的长度。其中， X i ={x 1 ,x 2 ,…,x i }；Y j ={y 1 ,y 2 ,…,y j }。当 i=0 或 j=0 时，空序列是 X i 和 Y j 的最长公共子序列。故此时 C[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：

　       j ij iy x j iy x j ij ij i c j i cj i c j i c; 0 ,; 0 ,0 , 0]} ][ 1 [ ], 1 ][ [ max{1 ] 1 ][ 1 [0] ][ [

　（3）计算最优值：算法 lcsLength 以序列 X={x1,x2…xm}和 Y={y1，y2…ym}作为输入。输出两个数组 c 和 b。其中，c[i][j]存储 Xi 和 Yj 的最长公共子序列的长度，b[i][j]记录 c[i][j]的值是由哪一个子问题的解得到的，问题的最优值存放于 c[m][n]中

　public static int lcsLength ( char[]x, char[]y, int[][]b)

　 {

　 int m=x.length-1;

　 int n=y.length-1;

　 int[][]c= new int[m+1][n+1];

　 for( int i=1;i<=m;i++)c[i][0]=0;

　 for( int i=1;i<=n;i++)c[0][i]=0;

　 for( int i=1;i<=m;i++)

　for( int j=1;j<=n;j++)

　{

　 f if(x[i]==y[j])

　 {

　 c[i][j]=c[i-1][j-1]+1;

　 b[i][j]=1;

　 }

　 else f if(c[i-1][j]>=c[i][j-1])

　 {

　c[i][j]=c[i-1][j];

　b[i][j]=2;

　 }

　 else

　 {

　c[i][j]=c[i][j-1];

　b[i][j]=3;

　 }

　}

　 return c[m][n];

　} （4）构造最优解：

　public static void lcs( int i, int j, char[]x, int[][]b)

　{

　 f if(i==0||j==0) return;

　 f if(b[i][j]==1){

　lcs (i-1,j-1,x,b);

　System. out .print(x[i]);

　 }

　 else f if(b[i][j]==2) lcs (i-1,j,x,b);

　 else lcs (i,j-1,x,b);

　} 2.2 程序源码

　最长公共子序列代码：

　/**

　 * 下面是最长公共子序列问题的动态规划算法

　 * char[]x={"A","B","C","D","A","B"};

　* char[]y={"B","D","C","A","B","A"};

　* 打印结果为CAB

　* @author zhanlingxia */

　package zuichanggonggongzixulie;

　public class zuichanggonggongzixulie {

　/*计算最优值

　 c[i][j]存储Xi和Yi的最长公共子序列的长度

　 b[i][j]记录c[i][j]的值是由最长公共子序列*/

　public static int lcsLength ( char[]x, char[]y, int[][]b)

　{

　 int m=x.length-1;

　 int n=y.length-1;

　 int[][]c= new int[m+1][n+1];

　 //空序列最长公共子序列

　 for( int i=1;i<=m;i++)c[i][0]=0;

　 for( int i=1;i<=n;i++)c[0][i]=0;

　 //对角线+1

　 for( int i=1;i<=m;i++)

　for( int j=1;j<=n;j++)

　{

　 f if(x[i]==y[j])

　 {

　 c[i][j]=c[i-1][j-1]+1;

　 b[i][j]=1;

　 }

　 //和上面一样

　 else f if(c[i-1][j]>=c[i][j-1])

　 {

　c[i][j]=c[i-1][j];

　b[i][j]=2;

　 }

　 //和左边一样

　 else

　 {

　c[i][j]=c[i][j-1];

　 b[i][j]=3;

　 }

　}

　 return c[m][n];

　}

　//打印最长公共子序列

　public static void lcs( int i, int j, char[]x, int[][]b)

　{

　 f if(i==0||j==0) return;

　 f if(b[i][j]==1){

　lcs (i-1,j-1,x,b);

　System. out .print(x[i]);

　 }

　 else f if(b[i][j]==2) lcs (i-1,j,x,b);

　 else lcs (i,j-1,x,b);

　}

　public static void main(String args[])

　{

　 char[]x={"A","B","C","D","A","B"};

　 char[]y={"B","D","C","A","B","A"};

　 int[][]b= new int[x.length+1][y.length+1];

　 System. out .println("最长公共子序列：");

　 int n= lcsLength (x,y,b);

　 System. out .println();

　 System. out .println("其长度为："+n);

　 System. out .println("最长公共子序列为：");

　 lcs (x.length-1,y.length-1,x,b);

　}

　} 2.3

　实验结论

　 4 2.4 心得体会：

　最长公共子序列比较好理解哦。做起来也相较简单多了 3 3

　0 0- -1 1 背包 问题

　 3.1 算法设计思想

　(1) 分析最优解：

　设(y 1 ,y 2 ,…,y n )是所给 0-1 背包问题的一个最优解，则 (y 2 ,…,y n )是下面相应子问题的一个最优解。

　nii i xv2max

　   n i xy w C x winii i2 }, 1 , 0 {1 12

　(2)建立递归关系：

　设所给 0-1 背包问题的子问题 ni kk k xv max

　  n k i xj x wkni kk k}, 1 , 0 { 的最优值为 m(i，j)，即 m(i，j)是背包容量为 j，可选择物品为 i，i+1，…，n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性质，可以建立计算 m(i，j)的递归式如下。

　ii i iw jw jj i mv w j i m j i mj i m    0 ) , 1 (} ) , 1 ( ), , 1 ( max{) , (

　nn nw jw j vj n m 0 0) , (

　（3）计算最优值：

　public static void knapsack( int[] v, int[] w, n int t c, int[][] m)

　 {

　int n = v.length-1;

　 int jMax = Math. min (w[n]-1, c);

　 for( int j = 0; j <= jMax; j++)

　m[n][j] = 0;

　//当w[n]>j 有 m[n][j]=0

　 //m[n][j] 表示只有n物品，背包的容量为j时的最大价值

　 for ( int j = w[n]; j <= c; j++)

　 m[n][j] = v[n];

　//当w[n]<=j 有m[n][j]=v[n]

　 //递规调用求出m[][]其它值，直到求出m[0][c]

　 for( int i = n-1; i >=1; i--)

　 {

　 jMax = Math. min (w[i]-1,c);

　for( int j = 0; j<=jMax; j++)

　 m[i][j] = m[i+1][j];

　 for( int j = w[i]; j <= c; j++)

　 m[i][j] = Math. max (m[i+1][j],m[i+1][j-w[i]]+v[i]);

　 }

　 m[0][c] = m[1][c];

　 f if(c >= w[0])

　 m[0][c] = Math. max (m[0][c],m[1][c-w[0]]+v[0]);

　 System. out .println(+m[0][c]);

　 }

　（4）构造最优解：

　public static void traceback( int[][] m, int[] w, int c, int[] x)

　{// 根据最优值求出最优解

　 int n = w.length-1;

　 for( int i = 0; i<n;i++)

　 f if(m[i][c] == m[i+1][c])

　 x[i] = 0;

　 else{

　 x[i] = 1;

　 c -= w[i];

　 }

　 x[n] = (m[n][c]>0)?1:0;

　 }

　3.2 程序源码 0 0- -1 1 背包问题 代码：

　/**

　 * 下面是0-1的动态规划算法

　 *v[] w[] c 分别是价值、重量、和背包容量数组

　*m[i][j]表示有i~n个物品，背包容量为j的最大价值。

　* @author zhanlingxia

　*/

　 public class beibao {

　 public static void knapsack( int[] v, int[] w, int c, int[][] m)

　 {

　int n = v.length-1;

　 int jMax = Math. min (w[n]-1, c);

　 for( int j = 0; j <= jMax; j++)

　m[n][j] = 0;

　//当w[n]>j 有 m[n][j]=0

　 //m[n][j] 表示只有n物品，背包的容量为j时的最大价值

　 for ( int j = w[n]; j <= c; j++)

　 m[n][j] = v[n];

　//当w[n]<=j 有m[n][j]=v[n]

　 //递规调用求出m[][]其它值，直到求出m[0][c]

　 for( int i = n-1; i >=1; i--)

　 {

　 jMax = Math. min (w[i]-1,c);

　for( int j = 0; j<=jMax; j++)

　m[i][j] = m[i+1][j];

　 for( int j = w[i]; j <= c; j++)

　 m[i][j] = Math. max (m[i+1][j],m[i+1][j-w[i]]+v[i]);

　 }

　 m[0][c] = m[1][c];

　 f if(c >= w[0])

　 m[0][c] = Math. max (m[0][c],m[1][c-w[0]]+v[0]);

　 System. out .println(+m[0][c]);

　 }

　public static void traceback( int[][] m, int[] w, int c, int[] x)

　 {// 根据最优值求出最优解

　 int n = w.length-1;

　 for( int i = 0; i<n;i++)

　 f if(m[i][c] == m[i+1][c])

　 x[i] = 0;

　 else{

　 x[i] = 1;

　 c -= w[i];

　 }

　 x[n] = (m[n][c]>0)?1:0;

　 }

　 public static void main(String[] args)

　 {

　 //测试

　 int[] w = {2,2,6,5,4};

　 int[] v = {6,3,5,4,6};

　 int[][] m = new int[11][11];

　 System. out .println("0-1背包问题最优值：");

　 knapsack (v,w,10,m);

　 System. out .println("0-1背包问题最优解：");

　 int[] x= new int[w.length];

　 traceback (m,w,10,x);

　 for( int i = 0;i<x.length;i++)

　 System. out .print(x[i]);

　 } } 3.3

　实验结论

　4 3.4 心得体会

　 深夜了，我被 0-1 背包问题折磨了一晚上，总算搞定了；从伪代码到代码的历程好艰辛。不过还是有点成就感的