动态规划算法实验报告

动态规划算法实验报告动态规划算法实验报告/动态规划算法实验报告实验标题矩阵连乘2.最长公共子序列3.最大子段和凸多边形最优三角剖分5.流水作业调度6.0-1背包问题7、最优二叉搜索树6、0-1背包问题7.最优二叉搜索树6、0-1背包问题7、最优二叉搜索树实验目的掌握动态规划法的基本思想和算法设计的基本步骤。实验内容与源码矩阵连乘#include<iostream>#include<cstdlib>usingnamespacestd;constintsize=4;//ra,ca和rb,cb分别表示矩阵A和B的行数和列数voidmatriMultiply(inta[][4],intb[][4],intc[][4],intra,intca,intrb,intcb){if(ca!=rb)cerr<<"矩阵不可乘";for(inti=0;i<ra;i++)for(intj=0;j<cb;j++){intsum=a[i][0]*b[0][j];for(intk=1;k<ca;k++)sum+=a[i][k]*b[k][j];c[i][j]=sum;}}voidMatrixChain(int*p,intn,intm[][4],ints[][4]){for(inti=1;i<=n;i++)m[i][i]=0;//对角线for(intr=2;r<=n;r++)//外维for(inti=1;i<=n-r+1;i++)//上三角{intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}voidTraceback(inti,intj,ints[][4]){if(i==j){cout<<"A"<<i;}elseif(i+1==j){cout<<"(A"<<i<<"A"<<j<<")";}else{cout<<"(";Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<")";}}intmain(){intw;cout<<"矩阵个数:";cin>>w;intp[w],s[w][w];cout<<"输入矩阵A1维数:";cin>>p[0]>>p[1];for(inti=2;i<=w;i++){intm=p[i-1];cout<<"输入矩阵A"<<i<<"维数:";cin>>p[i-1]>>p[i];if(p[i-1]!=m){cout<<endl<<"维数不对,矩阵不可乘!"<<endl;exit(1);}}Traceback(1,w,s);return0;}运行结果最长公共子序列#include<cstring>#include<iostream>#defineN100usingnamespacestd;//str1存储字符串x,str2存储字符串ycharstr1[N],str2[N];//lcs存储最长公共子序列charlcs[N];//c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度intc[N][N];//flag[i][j]==0为str1[i]==str2[j]//flag[i][j]==1为c[i-1][j]>=s[i][j-1]//flag[i][j]==-1为c[i-1][j]<s[i][j-1]intflag[N][N];//求长度intLCSLength(char*x,char*y){inti,j;//分别取得x,y的长度intm=strlen(x);intn=strlen(y);for(i=1;i<=m;i++)c[i][0]=0;for(i=0;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;flag[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];flag[i][j]=1;}else{c[i][j]=c[i][j-1];flag[i][j]=-1;}}returnc[m][n];}//求出最长公共子序列char*getLCS(char*x,char*y,intlen,char*lcs){inti=strlen(x);intj=strlen(y);while(i&&j){if(flag[i][j]==0){lcs[--len]=x[i-1];i--;j--;}elseif(flag[i][j]==1)i--;elsej--;}returnlcs;}intmain(){inti;cout<<"请输入字符串x:"<<endl;cin>>str1;cout<<"请输入字符串y:"<<endl;cin>>str2;intlcsLen=LCSLength(str1,str2);cout<<"最长公共子序列长度:"<<lcsLen<<endl;char*p=getLCS(str1,str2,lcsLen,lcs);cout<<"最长公共子序列为:";for(i=0;i<lcsLen;i++)cout<<lcs[i]<<"";return0;}运行结果3.最大子段和//分治法求最大子段和#include<iostream>usingnamespacestd;intMaxSubSum(int*a,intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;//最大子段和在左边intleftsum=MaxSubSum(a,left,center);//最大子段和在右边intrightsum=MaxSubSum(a,center+1,right);//最大子段和在中间ints1=0;intlefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}sum=s1+s2;//前后子段和相加//判断最大子段和if(sum>leftsum)sum=leftsum;if(sum>rightsum)sum=rightsum;}returnsum;}intMaxSum(int*a,intn){returnMaxSubSum(a,1,n-1);}intmain(){inta[8]={2,-3,-5,4,1,7,1,-5};cout<<"最大子段和为:"<<MaxSum(a,8);return0;}//动态规划法#include<iostream>usingnamespacestd;intMaxSum(int*a,intn){intsum=0,b=0;for(inti=1;i<n;i++)//此处不能=n,{if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}returnsum;}intmain(){inta[8]={2,-3,-5,4,1,7,1,-5};cout<<"最大子段和为:"<<MaxSum(a,8);return0;}运行结果凸多边形最优三角剖分#include<iostream>#include<cmath>#include<cstdlib>#defineN50usingnamespacestd;structpoint{intx;inty;};intdistance(pointX,pointY)//两点距离{intdis=(Y.x-X.x)*(Y.x-X.x)+(Y.y-X.y)*(Y.y-X.y);return(int)sqrt(dis);}intw(pointa,pointb,pointc)//权值{returndistance(a,b)+distance(b,c)+distance(a,c);}boolJudgeInput()//判断是否能构成凸多边形{point*v;//记录凸多边形各顶点坐标int*total;//记录坐标在直线方程中的值intm,a,b,c;cout<<"请输入凸多边形顶点个数:";cin>>m;intM=m-1;for(inti=0;i<m;i++){cout<<"输入顶点v"<<i<<"的坐标:";cin>>v[i].x>>v[i].y;}//根据顶点坐标判断是否能构成一个凸多边形for(intj=0;j<m;j++){intp=0;intq=0;if(m-1==j){a=v[m-1].y-v[0].y;b=v[m-1].x-v[0].y;c=b*v[m-1].y-a*v[m-1].x;}else{a=v[j].y-v[j+1].y;b=v[j].x-v[j+1].x;c=b*v[j].y-a*v[j].x;}for(intk=0;k<m;k++){total[k]=a*v[k].x-b*v[k].y+c;if(total[k]>0){p=p+1;}elseif(total[k]<0){q=q+1;}}if((p>0&&q>0)||(p==0&&q==0)){cout<<"无法构成凸多边形!"<<endl;exit(1);}}}boolminWeightTriangulation()//计算最优值算法{intM;int**t,**s;point*v;for(inti=1;i<=M;i++)t[i][i]=0;for(intr=2;r<=M;r++)for(inti=1;i<=M-r+1;i++){intj=i+r-1;t[i][j]=t[i+1][j]+w(v[i-1],v[i],v[j]);s[i][j]=i;for(intk=i+1;k<i+r-1;k++){intu=t[i][k]+t[k+1][j]+w(v[i-1],v[k],v[j]);if(u<t[i][j]){t[i][j]=u;s[i][j]=k;}}}returntrue;}voidTraceback(inti,intj,int**s){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<"三角形:v"<<i-1<<"v"<<s[i][j]<<"v"<<j<<endl;}intmain(){int**s;//记录最优三角剖分中所有三角形信息int**t;//记录最优三角剖分所对应的权函数值point*v;//记录凸多边形各顶点坐标int*total;//记录坐标在直线方程中的值intM=0;t=newint*[N];s=newint*[N];for(inti=0;i<N;i++){t[i]=newint[N];s[i]=newint[N];}v=newpoint[N];total=newint[N];if(JudgeInput()){if(minWeightTriangulation()){Traceback(1,M,s);cout<<endl;cout<<"最优权值之和为:"<<t[1][M]<<endl;}}return0;}运行结果:流水作业调度#include<iostream>#defineN100usingnamespacestd;classJobtype{public:/*intoperator<=(Jobtypea)const{return(key<=a.key);}*/intkey;intindex;booljob;};voidsort(Jobtype*d,intn){inti,j;Jobtypetemp;boolexchange;//交换标志for(i=0;i<n;i++){//最多做n-1趟排序exchange=false;//本趟排序开始前,交换标志应为假for(j=n-1;j>=i;j--)if(d[j+1].key<d[j].key){temp=d[j+1];d[j+1]=d[j];d[j]=temp;exchange=true;//发生了交换,故将交换标志置为真}if(!exchange)//本趟排序未发生交换,提前终止算法return;}}intFlowShop(intn,int*a,int*b,int*c){Jobtype*d=newJobtype[n];for(inti=0;i<n;i++)//初始化{d[i].key=a[i]>b[i]?b[i]:a[i];//执行时间d[i].job=a[i]<=b[i];//作业组d[i].index=i;//作业序号}sort(d,n);;intj=0;intk=n-1;for(inti=0;i<n;i++)//最优调度{if(d[i].job){c[j++]=d[i].index;}else{c[k--]=d[i].index;}}j=a[c[0]];k=j+b[c[0]];for(inti=1;i<n;i++){j+=a[c[i]];k=j<k?k+b[c[i]]:j+b[c[i]];}deleted;//回收空间returnk;//返回调度时间}intmain(){intn,*a,*b,*c;cout<<"作业数:";cin>>n;Jobtype*d=newJobtype[N];a=newint[N];b=newint[N];c=newint[N];cout<<"请输入作业号和时间:";for(inti=0;i<n;i++){cin>>d[i].index>>d[i].key;}cout<<endl;intk=FlowShop(n,a,b,c);cout<<"\n调度时间:"<<k<<endl;cout<<"最优调度序列:";for(inti=0;i<n;i++)//输出最优调度序列{cout<<c[i]<<"";}return0;}运行结果:6.0-1背包问题#include<iostream>#include<iomanip>usingnamespacestd;constintC=10;//容量constintN=5;//个数intmax(constinta,constintb){returna>b?a:b;}intmin(constinta,constintb){returna<b?a:b;}/*m为记录数组m[i][j]代表在剩有j容量的条件下,从i开始往后的物品中可以取得的最大价值w为重量数组,v为价值数组n为物品个数,c为开始容量则m[1][c]即此背包能剩下的最大价值*/voidknapsack(int**m,intn,intc,int*w,int*v){intjMax=min(w[n]-1,c);//前n-1个物品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;i>1;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]);}//找出最优解,0表示不能装,1表示能装voidtraceback(int**m,intn,intc,int*x,int*w){for(inti=1;i<n;i++){if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}}x[n]=(m[n][c]==0)?0:1;}intmain(){int*v=newint[N+1];int*w=newint[N+1];int**m=newint*[N+1];int*x=newint[N+1];for(inti=0;i<N+1;i++){m[i]=newint[C+1];}cout<<"输入重量序列,"<<N<<"个"<<endl;for(inti=1;i<=N;i++)cin>>w[i];cout<<"输入价值序列,"<<N<<"个"<<endl;for(inti=1;i<=N;i++)cin>>v[i];knapsack(m,N,C,w,v);traceback(m,N,C,x,w);cout<<"最优值:"<<m[1][C]<<endl;cout<<"是否装入背包的情况:";for(inti=1;i<=N;i++){cout<<x[i];}for(inti=0;i<N+1;i++){deletem[i];}delete[]m;return0;}运行结果最优二叉搜索树#include<iostream>#include<cmath>#include<limits>#defineN100usingnamespacestd;constdoubleMAX=numeric_limits<double>::max();//double的最大值//a[i]为结点i被访问的概率//b[i]为"虚结点"i被访问的概率//m[i][j]用来存放子树(i,j)的期望代价//w[i][j]用来存放子树（i,j）的所有结点（包括虚结点）的a,b概率之和//s[i][j]用来跟踪root的voidOptimalBinarySearchTree(double*a,double