【2017年整理】实验02动态规划算法.doc

实验02动态规划算法 [实验目的] 掌握动态规划算法的基本方法 掌握动态规划算法中最优子结构的分析 掌握递归求解最优值的方法 掌握最优解的构造. [预习要求] 认真阅读算法设计教材,了解动态规划原理; 设计用动态规划算法求解矩阵连乘、最长公共子序列以及电路布线的java程序. [实验题] 给定n个矩阵{A1, A2, …,An}，其中，Ai与Ai+1是可乘的，计算这n个矩阵的连乘积。从中找出一种乘次数最少的计算次序。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。 [实验步骤] 设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 应用设计的算法和程序求解问题; 将程序整理成功能模块存盘备用. [实验报告要求] 阐述实验目的和实验内容; 阐述求解问题的算法原理; 提交实验程序的功能模块; 记录最终测试数据和测试结果。 [参考] 1.//矩阵连乘类 public class Matrix { private int MN; //表示矩阵链中矩阵的数目 private int[] p; //存放各个矩阵的维数 private int [][][]A; //存放要进行连乘的多个矩阵 private int [][]m; //用来存放Ai到Aj的最少乘次数 private int [][]s; //用来存放Ai到Aj的最后断开位置 // public Matrix() { MN=0; p=new int [MN]; } //构造函数,L为矩阵的数目 public Matrix(int L) { MN=L; p=new int [MN+1]; A=new int [MN][][]; m=new int [MN+1][MN+1]; s=new int [MN+1][MN+1]; //随机生成连乘矩阵的维数[1-11] for(int i=0;i=MN;i++) { p[i]=(int) Math.round(Math.random()*10)+1; } //随机生成各个矩阵 for(int i=0;iMN;i++) { A[i]=new int [p[i]][p[i+1]]; CreatMatrix(A[i],p[i],p[i+1]); } } //创建矩阵a，维数为m*n private void CreatMatrix(int [][]a,int m,int n) { for(int i=0;im;i++) for(int j=0;jn;j++) a[i][j]=(int) Math.round(Math.random()*99)-50; } //输出连乘的所有矩阵 private void printAllM() { for (int i=0;ithis.MN;i++) { System.out.println(A+(i+1)+: +A[i].length +*+A[i][0].length ); printM(A[i]); } } //输出矩阵a的每个元素 private void printM(int [][]a) { for(int i=0;ia.length ;i++) { System.out.print( ); for(int j=0;ja[i].length;j++) System.out.print(String.format(%4d, a[i][j])); System.out.println(); } } public static void main(String [] args) { Matrix M=new Matrix(7); M.printAllM(); M.matrixChain(M.p,M.m,M.s); System.out.print(矩阵链所需的最少乘次数为：+M.m[1][M.MN]); System.out.println(); String []s=new String[M.MN+1]; for(int i=1;i=M.MN;i++) { s[i]=A+i; } M.traceback(M.s, 1, M.M