实验02动态规划算法

《实验02动态规划算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、-实验02动态规划算法[实验目的]1.掌握动态规划算法的基本方法2.掌握动态规划算法中最优子结构的分析3.掌握递归求解最优值的方法4.掌握最优解的构造.[预习要求]1.认真阅读算法设计教材,了解动态规划原理;2.设计用动态规划算法求解矩阵连乘、最长公共子序列以及电路布线的java程序.[实验题]1.给定n个矩阵{A1,A2,…,An}，其中，Ai与Ai+1是可乘的，计算这n个矩阵的连乘积。从中找出一种乘次数最少的计算次序。2.给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。3.在一块电路板的上、下2端分别有n个接线柱。根据电路设计

2、，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。[实验步骤]1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;2.应用设计的算法和程序求解问题;3.将程序整理成功能模块存盘备用.[实验报告要求]1.阐述实验目的和实验内容;2.阐述求解问题的算法原理;3.提交实验程序的功能模块;4.记录最终测试数据和测试结果。[参考]1.//矩阵连乘类publicclassMatrix{privateintMN;//表示矩阵链中矩阵的数目p

3、rivateint[]p;//存放各个矩阵的维数privateint[][][]A;//存放要进行连乘的多个矩阵privateint[][]m;//用来存放Ai到Aj的最少乘次数.---privateint[][]s;//用来存放Ai到Aj的最后断开位置//publicMatrix(){MN=0;p=newint[MN];}//构造函数,L为矩阵的数目publicMatrix(intL){MN=L;p=newint[MN+1];A=newint[MN][][];m=newint[MN+1][MN+1];s=newint[MN+1][MN+1];//随机生成连乘矩阵的维数[1-11]

4、for(inti=0;i<=MN;i++){p[i]=(int)Math.round(Math.random()*10)+1;}//随机生成各个矩阵for(inti=0;i

5、//输出连乘的所有矩阵privatevoidprintAllM(){for(inti=0;i

6、4d",a[i][j]));System.out.println();}}publicstaticvoidmain(String[]args){MatrixM=newMatrix(7);M.printAllM();M.matrixChain(M.p,M.m,M.s);System.out.print("矩阵链所需的最少乘次数为："+M.m[1][M.MN]);System.out.println();String[]s=newString[M.MN+1];for(inti=1;i<=M.MN;i++){s[i]="A"+i;}M.traceback(M.s,1,M.MN,s);fo

7、r(inti=1;i<=M.MN;i++){System.out.print(s[i]);}}//作用：计算a，b矩阵的乘积，将结果保存在c中，//参数：ra为a的行数，ca为a的列数，rb为b的行数，cb为b的列数publicstaticvoidmatrixMultiply(int[][]a,int[][]b,int[][]c,intra,intca,intrb,intcb){if(ca!=rb)thrownewIllegalArgumentException("矩