動態(tài)規(guī)劃算法實驗報告動態(tài)規(guī)劃算法實驗報告/動態(tài)規(guī)劃算法實驗報告實驗標題矩陣連乘2.最長公共子序列3.最大子段和凸多邊形最優(yōu)三角剖分5.流水作業(yè)調(diào)度6.0-1背包問題7、最優(yōu)二叉搜索樹6、0-1背包問題7.最優(yōu)二叉搜索樹6、0-1背包問題7、最優(yōu)二叉搜索樹實驗目的掌握動態(tài)規(guī)劃法的基本思想和算法設計的基本步驟。實驗內(nèi)容與源碼矩陣連乘#include<iostream>#include<cstdlib>usingnamespacestd;constintsize=4;//ra,ca和rb,cb分別表示矩陣A和B的行數(shù)和列數(shù)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<<"矩陣個數(shù):";cin>>w;intp[w],s[w][w];cout<<"輸入矩陣A1維數(shù):";cin>>p[0]>>p[1];for(inti=2;i<=w;i++){intm=p[i-1];cout<<"輸入矩陣A"<<i<<"維數(shù):";cin>>p[i-1]>>p[i];if(p[i-1]!=m){cout<<endl<<"維數(shù)不對,矩陣不可乘!"<<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;}//動態(tài)規(guī)劃法#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;}運行結果凸多邊形最優(yōu)三角剖分#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<<"請輸入凸多邊形頂點個數(shù):";cin>>m;intM=m-1;for(inti=0;i<m;i++){cout<<"輸入頂點v"<<i<<"的坐標:";cin>>v[i].x>>v[i].y;}//根據(jù)頂點坐標判斷是否能構成一個凸多邊形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()//計算最優(yōu)值算法{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;//記錄最優(yōu)三角剖分中所有三角形信息int**t;//記錄最優(yōu)三角剖分所對應的權函數(shù)值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<<"最優(yōu)權值之和為:"<<t[1][M]<<endl;}}return0;}運行結果:流水作業(yè)調(diào)度#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;//發(fā)生了交換,故將交換標志置為真}if(!exchange)//本趟排序未發(fā)生交換,提前終止算法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];//執(zhí)行時間d[i].job=a[i]<=b[i];//作業(yè)組d[i].index=i;//作業(yè)序號}sort(d,n);;intj=0;intk=n-1;for(inti=0;i<n;i++)//最優(yōu)調(diào)度{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;//返回調(diào)度時間}intmain(){intn,*a,*b,*c;cout<<"作業(yè)數(shù):";cin>>n;Jobtype*d=newJobtype[N];a=newint[N];b=newint[N];c=newint[N];cout<<"請輸入作業(yè)號和時間:";for(inti=0;i<n;i++){cin>>d[i].index>>d[i].key;}cout<<endl;intk=FlowShop(n,a,b,c);cout<<"\n調(diào)度時間:"<<k<<endl;cout<<"最優(yōu)調(diào)度序列:";for(inti=0;i<n;i++)//輸出最優(yōu)調(diào)度序列{cout<<c[i]<<"";}return0;}運行結果:6.0-1背包問題#include<iostream>#include<iomanip>usingnamespacestd;constintC=10;//容量constintN=5;//個數(shù)intmax(constinta,constintb){returna>b?a:b;}intmin(constinta,constintb){returna<b?a:b;}/*m為記錄數(shù)組m[i][j]代表在剩有j容量的條件下,從i開始往后的物品中可以取得的最大價值w為重量數(shù)組,v為價值數(shù)組n為物品個數(shù),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]);}//找出最優(yōu)解,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<<"最優(yōu)值:"<<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;}運行結果最優(yōu)二叉搜索樹#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