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

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

2、;i+) c0i=0; for(i=1;i=m;i+) for(j=1;j=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 width)if(i=0 | j=0) return; int k=i*(width+1)+j; if(bk=) LCS(i-1,j-1,x,b,width); coutxiendl; else if(bk=|) LCS(i-1,j,x,b,width); else LCS(i,j-1,x,b,w

3、idth); void main()char xmax=a,b,c,b,d,a,b; char ymax=b,d,c,a,b,a; int m=7; int n=6; char bmax=0;LCSLength(m,n,x,y,b); LCS(m,n,x,b,n);coutendl0;xi=yi时,cij=ci-1j-1+1当i,j0;xi!=yi时,cij=maxcij-1,ci-1j#include#define max(a,b) ab?a:b#define M 100void display(int &n,int &C,int wM,int vM)int i; coutn; couten

4、dl; coutC; coutendl; cout请输入各物品的大小或重量w:endl;w0=0; for(i=1;iwi; cout请输入各物品其价值v:endl;v0=0; for(i=1;ivi;int knapsack(int &n,int &C,int wM,int vM,int VMM) int i,j; for (i=0;i=n;i+)for(j=0;jj)Vij=Vi-1j;else if(wi=j) Vij=max(Vi-1j,Vi-1j-wi+vi);return VnC;void traceback(int n,int C,int wM,int xM,int VMM)fo

5、r(int i=1;i0)?1:0;void main()int i,j,n,C;char ch; int wM,vM,xM; int VMM;while(1)display(n,C,w,v);cout运算结果如下：endl;for(i=1;i=n;i+)xi=0;knapsack(n,C,w,v,V);cout ;for(j=0;j=C;j+)coutj ;coutendl;for(i=0;i=n;i+)couti ;for(j=0;j=C;j+)coutVij ;coutendl;coutendl;cout选择的物向量表示为:;cout ( ;traceback(n,C,w,x,V);for(i=1;i=n;i+)coutxi ;cout)endl;cou