用动态规划法解决最长公共子序列问题.doc

《用动态规划法解决最长公共子序列问题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、动态规划解最长子序列一、课程设计目的掌握动态规划法的原理，并能够按其原理编程实现求两个序列数据的最长公共子系列，以加深对其的理解。二、课程设计内容1、用动态规划法解决最长子序列问题2、交互输入两个序列数据3、输出两个序列的最长公共子序列三、概要设计四、详细设计与实现#include"iostream.h"#include"iomanip.h"#definemax100voidLCSLength(intm,intn,char*x,char*y,char*b){inti,j,k;intc[max][max];for(i=1;

2、i<=m;i++){c[i][0]=0;}for(i=1;i<=n;i++){c[0][i]=0;}for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;k=i*(n+1)+j;b[k]='\';}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];k=i*(n+1)+j;b[k]='

3、';}else{c[i][j]=c[i][j-1];k=i*(n+1)+j;b[k]='-';

4、}}}}voidLCS(inti,intj,char*x,char*b,intwidth){if(i==0

5、

6、j==0)return;intk=i*(width+1)+j;if(b[k]=='\'){LCS(i-1,j-1,x,b,width);cout<

7、'){LCS(i-1,j,x,b,width);}else{LCS(i,j-1,x,b,width);}}voidmain(){charx[max]={'a','b','c','b','d','a','b'};c

8、hary[max]={'b','d','c','a','b','a'};intm=7;intn=6;charb[max]={0};LCSLength(m,n,x,y,b);LCS(m,n,x,b,n);cout<

9、1] 的最长公共子序列2、若 xm != yn ，且 zk != xm , 则 Z 是 X[m-1] 和 Y 的最长公共子序列3、若 xm != yn , 且 zk != yn , 则 Z 是 Y[n-1] 和 X 的最长公共子序列由性质导出子问题的递归结构当 i = 0 , j = 0 时 , c[i][j] = 0当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1]

10、 , c[i-1][j] }#include#definemax(a,b)a>b?a:b#defineM100voiddisplay(int&n,int&C,intw[M],intv[M]){inti;cout<<"请输入物品种数n:";cin>>n;cout<>C;cout<>w[i];cout<<"请输入各物品其

11、价值v:"<>v[i];};intknapsack(int&n,int&C,intw[M],intv[M],intV[M][M]){inti,j;for(i=0;i<=n;i++)for(j=0;j<=C;j++){if(i==0

12、

13、j==0)V[i][j]=0;elseif(w[i]>j)V[i][j]=V[i-1][j];elseif(w[i]<=j)V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);}return

14、V[n][C];};voidtraceback(intn,intC,intw[M],intx[M],intV[M][M]){for(inti=1;i<=n;i++){if(V[i][C]==V[i-1][C])x[i]=0;else{x[i]=1;C=C-w[i];}}//x[n]=(V[n][C]>0)?1:0;}