《用动态规划法解决最长公共子序列问题.doc》由会员分享，可在线阅读，更多相关《用动态规划法解决最长公共子序列问题.doc（10页珍藏版）》请在三一文库上搜索。
1、用动态规划法解决最长公共子 序列问题动态规划解最长子序列一、课程设计目的掌握动态规划法的原理，并能够按其原理编 程实现求两个序列数据的最长公共子系列，以加 深对其的理解。二、课程设计内容1、用动态规划法解决最长子序列问题2、交互输入两个序列数据3、输出两个序列的最长公共子序列三、概要设计四、详细设计与实现#in elude "iostream.h"#in elude "ioma nip.h"#defi ne max 100voidLCSLe ngth(i ntm,i nt n ,char *x,char*y,char *b)int i,j,k;int c
2、maxmax;for(i=1;i<=m;i+)ci0=0；for(i=1;i<=n ;i+)cOi=O；for(i=1;i<=m;i+)for(j=1;j<=n ;j+)if(xi-1=yj-1) cij=ci-1j-1+1; k=i* (n+1)+j;bk=''else if(ci-1j>=cij-1)cij=ci-1j;k=i* (n+1)+j; bk='|' else cij=cij-1;k=i*( n+1)+j; bk='-'void LCS(int i,int j,char *x,char *b,int w
3、idth) if(i=0 | j=0)return;int k=i*(width+1)+j;if(bk='W)LCS(i-1,j-1,x,b,width); cout<<xi<<e ndl;else if(bk='|')LCS(i-1,j,x,b,width);elseLCS(i,j-1,x,b,width);void mai n()char xmax='a','b','c','b','d','a','b' char ymax='
4、;b','d','c','a','b','a' int m=7;int n=6;char bmax=0;LCSLe ngth(m, n,x,y,b);LCS(m, n,x,b, n);cout«e ndl«e ndl;最长公共子序列冋题具有最优子结构性质设X = x1 , . , xm Y = y1，yn 及它们的最长子序列Z = z1 , . , zk 则1 、若 xm = yn ，贝V zk = xm = yn ，且Zk-1是Xm-1和丫n-1的最长公共子序列2 、若xm != yn
5、,且zk != xm ,则Z是Xm-1和丫的最长公共子 序列3 、 若 xm != yn ,且 zk != yn ,则Z 是 Yn-1和 X 的最长公共子序列由性质导出子问题的递归结构 当 i = 0 , j = 0 时,cij = 0 当 i, j > 0 ; xi = yi 时,cij = ci-1j-1 + 1 当 i , j > 0 ; xi != yi 时,cij = max cij-1 , c i-1j #in clude<iostream.h>#defi ne max(a,b) a>b?a:b#defi ne M 100void display(i
6、nt &n ,i nt & C,i nt wM,i nt vM) int i;cout<<"请输入物品种数n:"cin>>n;cout<<e ndl;coutvv"请输入背包总容量C:"ci n> >C;cout«e ndl;cout<<"请输入各物品的大小或重量w:"<<e ndl;w0=0;for(i=1;i<=n ;i+)ci n> >wi;cout<<"请输入各物品其价值v:"&l
7、t;<endl;v0=0;for(i=1;i<=n ;i+)cin> >vi;intkn apsack(i nt&n,int & C,i ntwM,i ntvM,i nt VMM)int i,j;for (i=0;i<=n ;i+)for(j=0;j<=C;j+)if(i=0|j=0)Vij=0;else if(wi>j)V【ij=V【i-1j;else if(wi<=j)V【i【j=max(Vi-1【j,V【i-1【j-wi+vi);retur n Vn 【C;；void traceback(i nt n,i nt C,i nt
8、 wM,i nt xM,i ntVMM)for( int i=1;i<=n ;i+)if(ViC=Vi-1C)xi=0;elsexi=1;C=C-wi;x n=(VnC>0)?1:0;void mai n()int i,j, n,C;char ch;int wM,vM,xM;int VMM;whiledisplay( n,C,w,v);"<<e ndl;cout<<"运算结果如下： for(i=1;i<=n ;i+) xi=0;kn apsack( n,C,w,v,V); cout<<" " for(
9、j=0;j<=C;j+) cout<<j<<" "cout<<e ndl;for(i=0;i<=n ;i+)cout<<i<<" "for(j=0;j<=C;j+) cout«Vijvv""cout«e ndl; cout«e ndl;cout<<"选择的物向量表示为cout«"("traceback( n,C,w,x,V);for(i=1;i<=n ;i+) cout<<xi<<""cout<<")"<<e ndl;大 价 值否则按任意键cout<<" 背 包 最 为:"<<V nC<<e ndl;cout<<e ndl;cout<<"按Y或y继续操作, "<<e ndl;cin> >ch;if(ch=' Y'|ch='y') con ti nue;elsebreak;