实验二动态规划算法

实验二动态规划算法基本题一：最长公共子序列问题一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。三、程序代码#includestdlib.h#includeiostreamusingnamespacestd;voidLCSLength(intm,intn,char*x,char*y,int**c,int**b){inti,j;for(i=1;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]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);printf(%c,x[i]);}elseif(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}constintM=7;constintN=6;voidoutput(char*s,intn);voidLCSLength(intm,intn,char*x,char*y,int**c,int**b);voidLCS(inti,intj,char*x,int**b);voidmain(){//X={A,B,C,B,D,B,C}//Y={B,D,C,D,B,A}charx[]={'','A','B','C','B','D','B','C'};chary[]={'','B','D','C','D','B','A'};int**c=newint*[M+1];int**b=newint*[M+1];for(inti=0;i=M;i++){c[i]=newint[N+1];b[i]=newint[N+1];}cout序列X：endl;output(x,M);cout序列Y：endl;output(y,N);LCSLength(M,N,x,y,c,b);cout序列X、Y最长公共子序列长度为：c[M][N]endl;cout序列X、Y最长公共子序列为：endl;LCS(M,N,x,b);coutendl;}voidoutput(char*s,intn){for(inti=1;i=n;i++){couts[i];}coutendl;}四、运行结果分析：①在算法LCSLength中，由于每个数组单元的计算耗时O（1）时间，所以，算法LCSLength耗时O(m+n)。②在算法LCS中，每一次递归调用使i或j减1，因此算法的计算时间为O（m+n）。③在算法LCSLength和LCS中，可以将数组b省去，因为，数组元素c[i][j]的值仅由c[i-1][j-1],c[i-1][j]和c[i][j-1]这三个数组元素的值所确定。对于给定的数组元素c[i][j],可以不借助于数组b而仅借助与数组c本身在O(1)时间内确定c[i][j]的值。基本题二：最大字段和问题一、实验目的与要求1、熟悉最长最大字段和问题的算法；2、进一步掌握动态规划算法；二、实验题若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。三、程序代码#includeiostream.h#defineNUM1001inta[NUM];intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i=n;i++){intthissum=0;for(intj=i;j=n;j++){thissum+=a[j];if(thissumsum){sum=thissum;besti=i;bestj=j;}}}returnsum;}voidmain(){intn;intbesti,bestj;cout请输入数组的长度:endl;cinn;while(true){besti=0;bestj=0;cout请输入数组的内容,以空格隔开:endl;for(inti=1;i=n;i++)cina[i];cout最大子段和为:MaxSum(n,a,besti,bestj)endl;cout最大子段和的序列是从besti到bestjendl;break;}}四、运行结果分析：①本算法的计算时间为O(n^2)。②针对最大子段和这个具体问题本身的结构，还可以从算法设计的策略上对上述O(n^2)计算时间算法加以更深刻的改进。从问题的解的结构看出，可以用分治法求解。提高题一：用动态规划法求解0/1背包问题一、实验要求与目的1、掌握动态规划算法求解问题的一般特征和步骤。2、使用动态规划法编程，求解0/1背包问题。二、实验内容1、问题描述：给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？2、程序代码#includeiostreamusingnamespacestd;typedeffloatType;templateclassTypevoidKnapsack(Typev,intw,intc,intn,Type**m){intjMax=min(w[n]-1,c)for(intj=0;j=jMax;j++)m[n][j]=0;for(intj=w[n];j=c;j++)m[n][j]=v[n];for(inti=n-1;i1;i--){jMax=min(w[i]-1,c);for(intj=0;j=jMax;j++)m[i][j]=m[i+1][j];for(intj=w[i];j=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}templateclassTypevoidTraceback(Type**m,intw,intc,intn,intx){for(inti=1;in;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c])?1:0;}voidmain(){intc,i,n;TypemaxV;Typev[150];intw[150];cout请输入背包的最大容量:endl;cinc;cout输入物品数:endl;cinn;cout请分别输入物品的重量:endl;for(i=0;in;i++)cinw[i];cout请分别输入物品的价值:endl;for(i=0;in;i++)cinv[i];maxV=Knapsack(v,w,c,n,m);cout最大物品的价值为:endl;}3、程序实现；给出实例测试结果。三、实验总结本次试验让我们学会了怎样用算法实现求最长公共子序列和最大子段和问题，了解了如何对算法进行改进，怎样计算最优值；对于最大字段和问题，知道如何用分治法来求解，如何设计动态规划算法求解。对于本次实验，让我知道了实验的重要性，它比我们上课更重要，更有利于我们更好的掌握算法知识。