用動態(tài)規(guī)劃法解決最長公共子序列問題

1、 動態(tài)規(guī)劃解最長子序列一、 課程設(shè)計目的掌握動態(tài)規(guī)劃法的原理，并能夠按其原理編程實現(xiàn)求兩個序列數(shù)據(jù)的最長公共子系列，以加深對其的理解。二、 課程設(shè)計內(nèi)容1、用動態(tài)規(guī)劃法解決最長子序列問題2、交互輸入兩個序列數(shù)據(jù)3、輸出兩個序列的最長公共子序列三、 概要設(shè)計四、 詳細設(shè)計與實現(xiàn)#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運算結(jié)果如下：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