动态规划算法实验报告(共17页).doc

精选优质文档-倾情为你奉上实验标题1、 矩阵连乘 2、最长公共子序列 3、最大子段和 4、 凸多边形最优三角剖分 5、流水作业调度 6、0-1背包问题 7、最优二叉搜索树实验目的掌握动态规划法的基本思想和算法设计的基本步骤。实验内容与源码1、 矩阵连乘#include<iostream>#include<cstdlib>using namespace std;const int size=4;/ra,ca和rb,cb分别表示矩阵A和B的行数和列数void matriMultiply(int a4,int b4,int c4,int ra ,int ca,int rb ,int cb ) if(ca!=rb) cerr<<"矩阵不可乘" for(int i=0;i<ra;i+) for(int j=0;j<cb;j+) int sum=ai0*b0j; for(int k=1;k<ca;k+) sum+=aik*bkj; cij=sum; void MatrixChain(int *p,int n,int m4,int s4) for(int i=1;i<=n;i+) mii=0;/对角线 for(int r=2;r<=n;r+)/外维 for(int i=1;i<=n-r+1;i+)/上三角 int j=i+r-1; mij=mi+1j+pi-1*pi*pj; sij=i; for(int k=i+1;k<j;k+) int t=mik+mk+1j+pi-1*pk*pj; if(t<mij) mij=t; sij=k; void Traceback(int i,int j,int s4) if(i = j) cout<<"A"<<i; else if(i+1 = j) cout<<"(A"<<i<<"A"<<j<<")" else cout<<"(" Traceback(i,sij,s); Traceback(sij+1,j,s); cout<<")" int main() int w; cout<<"矩阵个数：" cin>>w; int pw,sww; cout<<"输入矩阵A1维数：" cin>>p0>>p1; for(int i=2 ; i<=w ; i+) int m = pi-1; cout<<"输入矩阵A"<<i<<"维数：" cin>>pi-1>>pi; if(pi-1 != m) cout<<endl<<"维数不对，矩阵不可乘！"<<endl; exit(1); Traceback(1,w,s); return 0;运行结果2、 最长公共子序列#include<cstring>#include<iostream>#define N 100using namespace std;/str1存储字符串x，str2存储字符串ychar str1N,str2N;/lcs存储最长公共子序列char lcsN;/cij存储str11.i与str21.j的最长公共子序列的长度int cNN;/flagij=0为str1i=str2j/flagij=1为ci-1j>=sij-1/flagij=-1为ci-1j<sij-1int flagNN;/求长度int LCSLength(char *x, char *y) int i,j; /分别取得x,y的长度 int m = strlen(x); int n = strlen(y); for(i=1;i<=m;i+) ci0 = 0; for(i=0;i<=n;i+) c0i = 0; for(i=1;i<=m;i+) for(j=1;j<=n;j+) if(xi-1=yj-1) cij = ci-1j-1 +1; flagij = 0; else if(ci-1j>=cij-1) cij = ci-1j; flagij = 1; else cij = cij-1; flagij = -1; return cmn;/求出最长公共子序列char* getLCS(char *x, char *y,int len,char *lcs) int i = strlen(x); int j = strlen(y); while(i&&j) if(flagij=0) lcs-len = xi-1; i-; j-; else if(flagij=1) i-; else j-; return lcs;int main() int i; cout<<"请输入字符串x："<<endl; cin>>str1; cout<<"请输入字符串y："<<endl; cin>>str2; int lcsLen = LCSLength(str1,str2); cout<<"最长公共子序列长度："<<lcsLen<<endl; char *p = getLCS(str1,str2,lcsLen,lcs); cout<<"最长公共子序列为：" for(i=0;i<lcsLen;i+) cout<<lcsi<<" " return 0;运行结果3、最大子段和/分治法求最大子段和#include<iostream>using namespace std;int MaxSubSum(int *a,int left,int right) int sum=0; if(left=right) sum=aleft>0?aleft:0; else int center = (left+right)/2; /最大子段和在左边 int leftsum=MaxSubSum(a,left,center); /最大子段和在右边 int rightsum=MaxSubSum(a,center+1,right); /最大子段和在中间 int s1=0; int lefts=0; for(int i=center;i>=left;i-) lefts+=ai; if(lefts>s1) s1=lefts; int s2=0; int rights=0; for(int i=center+1;i<=right;i+) rights+=ai; if(rights>s2) s2=rights; sum=s1+s2;/前后子段和相加 /判断最大子段和 if(sum>leftsum)sum=leftsum; if(sum>rightsum) sum=rightsum; return sum;int MaxSum(int *a,int n) return MaxSubSum(a,1,n-1);int main() int a8=2,-3,-5,4,1,7,1,-5; cout<<"最大子段和为："<<MaxSum(a,8); return 0;/动态规划法#include<iostream>using namespace std;int MaxSum(int *a,int n) int sum=0,b=0; for(int i=1;i<n;i+)/此处不能=n， if(b>0) b+=ai; else b=ai; if(b>sum) sum=b; return sum;int main() int a8=2,-3,-5,4,1,7,1,-5; cout<<"最大子段和为："<<MaxSum(a,8); return 0;运行结果4、 凸多边形最优三角剖分#include<iostream>#include<cmath>#include<cstdlib>#define N 50using namespace std;struct point int x; int y;int distance(point X, point Y)/两点距离 int dis = (Y.x-X.x)*(Y.x-X.x) + (Y.y-X.y)*(Y.y-X.y); return (int)sqrt(dis);int w(point a, point b, point c)/权值 return distance(a,b) + distance(b,c) + distance(a,c);bool JudgeInput()/判断是否能构成凸多边形 point *v; /记录凸多边形各顶点坐标 int *total; /记录坐标在直线方程中的值 int m,a,b,c; cout<<"请输入凸多边形顶点个数：" cin>>m; int M = m-1; for(int i=0 ; i<m ; i+) cout<<"输入顶点v"<<i<<"的坐标：" cin>>vi.x>>vi.y; /根据顶点坐标判断是否能构成一个凸多边形 for(int j=0 ; j<m ; j+) int p = 0; int q = 0; if(m-1 = j) a = vm-1.y - v0.y; b = vm-1.x - v0.y; c = b * vm-1.y - a * vm-1.x; else a = vj.y - vj+1.y; b = vj.x - vj+1.x; c = b * vj.y - a * vj.x; for(int k=0 ; k<m ; k+) totalk = a * vk.x - b * vk.y + c; if(totalk > 0) p = p+1; else if(totalk < 0) q = q+1; if(p>0 && q>0) | (p=0 && q=0) cout<<"无法构成凸多边形！"<<endl; exit(1); bool minWeightTriangulation()/计算最优值算法 int M; int *t, *s; point *v; for(int i=1 ; i<=M ; i+) tii = 0; for(int r=2 ; r<=M ; r+) for(int i=1 ; i<=M-r+1 ; i+) int j = i+r-1; tij = ti+1j + w(vi-1,vi,vj); sij = i; for(int k=i+1 ; k<i+r-1 ; k+) int u = tik + tk+1j + w(vi-1,vk,vj); if(u < tij) tij = u; sij = k; return true;void Traceback(int i, int j, int *s) if(i = j) return; Traceback(i,sij,s); Traceback(sij+1,j,s); cout<<"三角形：v"<<i-1<<"v"<<sij<<"v"<<j<<endl;int main() int *s; /记录最优三角剖分中所有三角形信息 int *t; /记录最优三角剖分所对应的权函数值 point *v; /记录凸多边形各顶点坐标 int *total; /记录坐标在直线方程中的值 int M=0; t = new int *N; s = new int *N; for(int i=0 ; i<N ; i+) ti = new intN; si = new intN; v = new pointN; total = new intN; if(JudgeInput() if(minWeightTriangulation() Traceback(1,M,s); cout<<endl; cout<<"最优权值之和为："<<t1M<<endl; return 0;运行结果：5、 流水作业调度#include<iostream>#define N 100using namespace std;class Jobtype public: /* int operator<=(Jobtype a)const return(key<=a.key); */ int key; int index; bool job;void sort(Jobtype *d,int n) int i,j; Jobtype temp; bool exchange; /交换标志 for(i = 0;i < n;i +) /最多做n-1趟排序 exchange = false; /本趟排序开始前，交换标志应为假 for(j = n - 1;j >= i;j -) if(dj+1.key < dj.key) temp = dj+1; dj+1 = dj; dj = temp; exchange=true; /发生了交换，故将交换标志置为真 if(!exchange) /本趟排序未发生交换，提前终止算法 return; int FlowShop(int n,int *a,int *b,int *c) Jobtype *d = new Jobtypen; for(int i=0;i<n;i+)/初始化 di.key=ai>bi?bi:ai;/ 执行时间 di.job=ai<=bi;/ 作业组 di.index=i;/作业序号 sort(d,n); int j=0; int k=n-1; for(int i=0;i<n;i+)/最优调度 if(di.job) cj+=di.index; else ck-=di.index; j=ac0; k=j+bc0; for(int i=1;i<n;i+) j+=aci; k=j<k?k+bci:j+bci; delete d;/回收空间 return k;/返回调度时间int main() int n,*a,*b,*c; cout<<"作业数：" cin>>n; Jobtype *d = new JobtypeN; a=new intN; b=new intN; c=new intN; cout<<"请输入作业号和时间：" for(int i=0;i<n;i+) cin>>di.index>>di.key; cout << endl; int k=FlowShop(n,a,b,c); cout<<"n调度时间："<<k<<endl; cout<<"最优调度序列:" for (int i = 0; i < n; i+) / 输出最优调度序列 cout << ci << " " return 0;运行结果：6、0-1背包问题#include <iostream>#include <iomanip>using namespace std;const int C=10;/容量const int N=5;/个数int max(const int a,const int b) return a>b?a:b;int min(const int a,const int b) return a<b?a:b;/*m为记录数组 mij代表在剩有j容量的条件下，从i开始往后的物品中可以取得的最大价值w为重量数组，v为价值数组n为物品个数，c为开始容量则m1c即此背包能剩下的最大价值*/void knapsack(int *m,int n, int c,int *w, int *v) int jMax = min(wn-1,c);/前n-1个物品 for(int j=0;j<=jMax;j+) mnj=0; for(int j=wn;j<=c;j+) mnj=vn; for(int i=n-1;i>1;i-) jMax=min(wi-1,c); for(int j=0;j<=jMax;j+) mij = mi+1j; for(int j=wi;j<=c;j+) mij = max(mi+1j,mi+1j-wi+vi); m1c=m2c; if(c>=w1) m1c=max(m1c,m2c-w1+v1);/找出最优解，0表示不能装，1表示能装void traceback(int *m,int n,int c,int *x,int *w) for(int i=1;i<n;i+) if(mic=mi+1c) xi=0; else xi=1; c-=wi; xn=(mnc=0)?0:1;int main() int *v=new intN+1; int *w=new intN+1; int *m=new int* N+1; int *x=new int N+1; for(int i=0;i<N+1;i+) mi=new intC+1; cout<<"输入重量序列,"<<N<<"个"<<endl; for(int i=1;i<=N;i+) cin>>wi; cout<<"输入价值序列,"<<N<<"个"<<endl; for(int i=1;i<=N;i+) cin>>vi; knapsack(m,N,C,w,v); traceback(m,N,C,x,w);cout<<"最优值："<<m1C<<endl;cout<<"是否装入背包的情况：" for(int i=1;i<=N;i+) cout<<xi; for(int i=0;i<N+1;i+) delete mi; delete m; return 0;运行结果7、 最优二叉搜索树#include<iostream>#include<cmath>#include<limits>#define N 100using namespace std;const double MAX = numeric_limits<double>:max(); /double的最大值/ai为结点i被访问的概率/bi为“虚结点”i被访问的概率/mij用来存放子树（i，j）的期望代价/wij用来存放子树（i，j）的所有结点（包括虚结点）的a,b概率之和/sij用来跟踪root的void OptimalBinarySearchTree(double *a,double *b,int n) int sNN; double mNN; double wNN; int i,j,l,r; for(i=1; i<=n+1; i+) mii-1 = bi-1; wii-1 = bi-1; for(l=1; l<=n; l+) for(i=1; i<=n-l+1; i+) j = l+i-1; mij = MAX; wij = wij-1 + aj +bj; for(r=i; r<=j; r+) double k = mir-1 + wij + mr+1j; if(k<mij) mij = k; sij = k; cout<<m1n;int main() double aN,bN; int n; double sum = 0; int i,j,l; cout<<"请输入关键字的个数："<<endl; cin>>n; cout<<"请输入每个关键字的概率："<<endl; for(i=1; i<=n; i+) cin>>ai; sum += ai; cout<<"请输入每个虚拟键的概率："<<endl; for(i=0; i<=n; i+) cin>>bi; sum += bi; if(abs(sum-1)>0.01) cout<<"输入的概率和不为1,请重新输入"<<endl; cout<<"最优二叉查找树的期望搜索代价为：" OptimalBinarySearchTree(a,b,n); return 0;运行结果：实验总结 通过实现动态规划的这个题目，对动态规划算法有了进一步的了解。先分析问题，判断是否具有最优子结果和重叠字问题的性质。专心-专注-专业