实验二 动态规划

实验报告

（2013—2014学年 第 1 学期）

课程名称 算法设计与分析 实验名称 实验二 动态规划 专 业 计算机科学与技术（非师范） 年 级 2011级 学号 B2011102109 姓名 陈阿婵 指导教师 石 曼 银 实验日期 2013-11-21

实验目的与要求： 1.通过动态规划算法的示例程序理解动态规划算法的基本思想； 2.运用动态规划算法解决实际问题加深对动态规划算法的理解和运用； 实验设备（环境）：windows XP 操作系统 微机 1台/人 实验内容： 1.分析并掌握“最长公共子序列” 问题的动态规划算法求解方法； 2.练习使用动态规划算法求解“游艇租用”问题； 实验步骤、实验结果及分析： 1. 分析并掌握“最长公共子序列” 问题的动态规划算法求解方法 对给定序列X=(x1, x2,„, xm)和序列Z=(z1, z2,„, zk)，Z是X的子序列当且仅当存在一个严格递增下标序列(i1, i2,„, ik)，使得对于所有j=1, 2, „, k，有zj=xij（1≤ij≤m）。 给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列问题就是在序列X和Y的公共子序列中查找长度最长的公共子序列。 分析： 要找出序列X={x1, x2,…, xm}和Y={y1, y2,…, yn}的最长公共子序列，可按下述递推方式计算：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm即可得到X和Y的最长公共子序列；当xm≠yn时，必须求解两个子问题：找出Xm-1和Y的最长公共子序列以及Xm和Yn-1的最长公共子序列，这两个公共子序列中的较长者即为X和Y的最长公共子序列。用L[i][j]表示子序列Xi和Yj的最长公共子序列的长度，可得如下动态规划函数： L[0][0]=L[i][0]=L[0][j]=0(1≤i≤m,1≤j≤n) （式6.14）

xiyj,i1,j1L[i1][j1]1（式6.15） L[i][j]xiyj,i1,j1max{L[i][j1],L[i1][j]} 算法描述： int CommonOrder(int m, int n, int x[ ], int y[ ], int z[ ]) { for (j=0; j<=n; j++) //初始化第0行 L[0][j]=0; for (i=0; j<=m; i++) //初始化第0列 L[i][0]=0; for (i=1; i<=m; i++) for (j=1; j<=n; j++) if (x[i]= =y[j]) { L[i][j]=L[i-1][j-1]+1; S[i][j]=1; } else if (L[i][j-1]>=L[i-1][j]) { L[i][j]=L[i][j-1]; S[i][j]=2; } else {L[i][j]=L[i-1][j]; S[i][j]=3; } i=m; j=n; k=L[m][n]; for (i>0 && j>0) { if (S[i][j]= =1) { z[k]=x[i]; k--; i--; j--; } else if (S[i][j]= =2) j--; else i--; } return L[m][n]; } 请分析“最长公共子序列” 问题的时间复杂性 2. 练习使用动态规划算法求解“游艇租用”问题 2.1 问题描述 长江游艇俱乐部在长江上设置了n个游艇出租站1，2，„，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r（i，j），1≤i #include int w[21],x[21][21],n; int solve(int h) { if(w[h]>0)return w[h]; if(h==n-1)return x[h][n]; int min=x[h][n]; for(int k=h+1;k>n; for(i=1;i>x[i][j]; } outfile<<\"所需最少费用：\"<