实验三 动态规划.doc

实验二 动态规划（一）、实验目的 通过编程实现动态规划的有关算法，理解动态规划的原理，掌握动态规划基本思想与应用技巧。（二）、实验题目与要求：实验题目1：最长公共子序列问题的算法若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。实验要求： 1 理解动态规划算法的原理，认真阅读题目。完善程序，实现该算法；2 结果显示最长公共子序列。 实验提示：先求最长公共子序列， X和Y的最长公共子序列的长度记录于cmn中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+1n+1; for (int i = 1; i = m; i+) ci0=0; for (int i = 1; i = n; i+) c0i=0; for (int i = 1; i = m; i+) for (int j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; return cmn; 然后构造最长公共子序列public static void lcs(int i,int j,char x,int b) if (i = =0 | j= =0) return; if (bij= = 1) lcs(i-1,j-1,x,b); System.out.print(xi); else if (bij= = 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); 实验题目2：用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，有aibi，而对于某些j，ji，有ajbj。既不能将一个作业分开由两台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这两台机器处理完成这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总时间）。实验要求： 1 理解动态规划算法的原理，认真阅读题目。完善程序，实现该算法；2 研究一个实例：(a1, a2, a3, a4, a5, a6) = (2, 5, 7, 10, 5, 2) ；(b1, b2, b3, b4, b5, b6）=(3, 8, 4, 11, 3, 4)。结果显示处理完所有作业的最短时间。实验题目3：计算矩阵连乘积给定n个矩阵A1,A2 ,.,An，其中Ai与Ai+1是可乘的，i=1,2,.,n-1。考察这n个矩阵的连乘积A1A2.An，给出其最优计算次序，使矩阵连乘运算乘法次数最少。实验要求： 1 理解动态规划算法的原理，认真阅读题目。完善程序，实现该算法；2 给定五个矩阵：A1：5*10；A2：10*4；A3：4*6； A4：6*10；A5：10*2，给出最优计算次序和乘法次数。实验提示：设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n。递归定义mi,j 为：public static 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-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 实验题目4：0-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?实验要求： 1 理解动态规划算法的原理，认真阅读题目。完善程序，实现该算法；2 自行设计输入数据和输出格式。实验提示：设n个物品的重量存储在数组wn中，价值存储在数组vn中，背包容量为C，数组Vn+1C+1存放迭代结果，其中Vij表示前i个物品装入容量为j的背包中获得的最大价值，数组xn存储装入背包的物品，动态规划法求解0/1背包问题的算法如下： public static int KnapSack(int C, int w , int v ,intV) int n=v.length; for (int i=0; i=n; i+) Vi0=0; /初始化第0列 for (int j=0; j=C; j+) V0j=0; /初始化第0行 for (int i=1; i=n; i+) /计算第i行，进行第i次迭代 for (int j=1; j=C; j+) if (j0; i-) if (VijVi-1j) xi=1; j-=wi; else xi=0; return VnC; /返回背包取得的最大价值（三）、实验步骤1. 对于以上题目要认真分析和理解题意，任选两个题目设计出算法；2. 详细写出正确的高级语言源程序；3. 上机录入并调试程序；4. 请指导教师审查程序和运行结果并评定成绩；5. 撰写并上交实验报告。（四）、实验报告内容1. 班级、学号、姓名、实验日期；2. 实验题目；3. 对于实验题目的理解与说明；4. 程序功能与框架；5. 设计说明（存储结构、特别构思等）；6. 调试报告