《用动态规划法解决最长公共子序列问题》由会员分享，可在线阅读，更多相关《用动态规划法解决最长公共子序列问题（6页珍藏版）》请在金锄头文库上搜索。
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;cout背包最大价值为:VnCendl;coutendl;cout按Y或y继续操作，否则按任意键ch;if(ch=Y|ch=y)continue;elsebreak;矮化砧嫁接的苹果树树冠体积小于乔化砧嫁接的苹果树树冠体积，矮化砧苹果树单株产量低于乔化砧苹果树，所以，栽植矮化苹果树必须根据不同的矮化砧木和不同类型的短枝型品种适当加大栽培密度
