动态规划算法实验报告材料

1、实验标题实验目的实验内容与源码1矩阵连乘 2、最长公共子序列3 、最大子段和4、凸多边形最优三角剖分5、流水作业调度6、0-1背包问题 7、最优二叉搜索树掌握动态规划法的基本思想和算法设计的基本步骤。1、矩阵连乘#in clude<iostream>#in clude<cstdlib>using n amespace std;const int size=4;ra,ca和rb,cb分别表示矩阵 A和B的行数和列数void matriMultiply(i nta4,i nt b4,i nt c4,i nt ra ,int ca,i ntrb ,int cb )if(ca!

2、=rb) cerr<<"矩阵不可乘"for(i nt i=0;i<ra;i+)for(i nt j=O;j<cb;j+)int sum=ai0*b0j;for(i nt k=1;k<ca;k+)sum+=aik*bkj;cij=sum;void MatrixChai n(int *p,i nt n,i nt m4,i nt s4)for(i nt i=1;i<=n;i+) mii=0;对角线for(i nt r=2;r<=n;r+)外维for(i nt i=1;i<=n-r+1;i+)上三角int j=i+r-1;mij=mi

3、+1j+pi-1*pi*pj;sij=i;for(i nt k=i+1;k<j;k+)int t=mik+mk+1j+pi-1*pk*pj;if(t<mij)mij=t;sij=k;void Traceback(i nt i,i nt j,i nt s4)if(i = j) cout<<"A"<<i;else if(i+1 = j)cout<<"(A"<<i<<"A"<<j<<")"elsecout<<&qu

4、ot;("Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<")"int mai n()int w;cout<<" 矩阵个数："cin> >w;int pw,sww;cout<<"输入矩阵A1维数："cin >>pO»p1；for(i nt i=2 ; i<=w ; i+)int m = pi-1;cout<<" 输入矩阵A"<<i<<"维数：

5、"cin> >pi_1»pi;if(pi-1 != m)"<<e ndl;cout<<e ndl<<"维数不对，矩阵不可乘!exit(1);Traceback(1,w,s);return 0;运行结果上«法8日巳矩阵连乘1巳炬叵卜数：勺阵蛆维数：2 3阵朋维数；3 4库A3维數：4 S (A1A2JA3)Mm 丄 c_丄:_on_ogA_.2、最长公共子序列#in clude<cstri ng>#in clude<iostream>#defi ne N 100using n

6、 amespace std;str1存储字符串x, str2存储字符串ychar str1N,str2N;/lcs存储最长公共子序列char lcsN;cij存储str11.i 与str21.j的最长公共子序列的长度int cNN;flagij=O/flagij=1 flagij=-1为 str1i=str2j为 ci-1j>=sij-1为 ci-1j<sij-1 int flagNN;/求长度int LCSLe ngth(char *x, char *y) int i,j;分别取得x,y的长度int m = strle n(x);int n = strle n( y); for(

7、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;elsecij = cij-1; flagij = -1;return cm n;/求出最长公共子序列char* getLCS(char *x, char *y,i nt le n, char *lcs) int i = strle n

8、( x);int j = strle n( y);while(i&&j)if(flagij=0)lcs-le n = xi-1;i-;j-;else if(flagij=1)i-;elsej-;return lcs; int mai n()int i;cout<<"请输入字符串x: "<<endl;cin> >str1;cout<<"请输入子符串y： "<<endl;cin> >str2;in t IcsLe n = LCSLe ngth(str1,str2);cou

9、t<<"最长公共子序列长度："<<lcsLe * <e ndl;char *p = getLCS(str1,str2,lcsLe n,lcs);cout<<"最长公共子序列为："for(i=0;i<lcsLe n;i+) cout<<lcsi<<""return 0;运行结果6 e亠-J :s 度：亠 列列 序序.-:子子 宇Eh字沪共共 入Lef入cf冬公 ab/ 产 1嗇se口IFK圭-3、最大子段和/分治法求最大子段和#in clude<iostrea

10、m>using n amespace std;int MaxSubSum(int *a,int left,int right)int sum=0;if(left=right) sum=aleft>O?aleft:O;elseint cen ter = (left+right)/2;/最大子段和在左边int leftsum=MaxSubSum(a,left,center);/最大子段和在右边int rightsum=MaxSubSum(a,ce nter+1,right);/最大子段和在中间int s1=0;int lefts=0;for(int i=center;i>=lef

11、t;i-)lefts+=ai;if(lefts>s1) s1=lefts;int s2=0;int rights=O;for(i nt i=cen ter+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(i nt *a,i nt n)return MaxSubSum(a,1, n-1);int mai n()i

12、nt a8=2,-3,-5,4,1,7,1,-5;cout<<"最大子段和为："<<MaxSum(a,8); return 0;/动态规划法#in clude<iostream>using n amespace std;int MaxSum(i nt *a,i nt n)int sum=0,b=0;for(i nt i=1;i< n;i+)此处不能=n，if(b>0) b+=ai;else b=ai;if(b>sum) sum=b;return sum;int mai n()int a8=2,-3,-5,4,1,7,1,

13、-5;cout<<"最大子段和为："<<MaxSum(a,8); return 0;运行结果赏大子段W为：13'Pracess returned 0 (0k0) ©Kecution time : 6 274 s Press any key to continue4、凸多边形最优三角剖分#in clude<iostream>#in clude<cmath>#in clude<cstdlib>#defi ne N 50using n amespace std;struct pointint x;int

14、 y;int dista nce(poi nt X, poi nt Y)两点距离int dis = (Y.x-X.x)*(Y.x-X.x) + (Y.y-X.y)*(Y.y-X.y); return (in t)sqrt(dis);int w(po int a, point b, point c)/权值retur n dista nce(a,b) + dista nce(b,c) + dista nce(a,c); 判断是否能构成凸多边形point *v;/bool Judge In put()int *total;/记录凸多边形各顶点坐标记录坐标在直线方程中的值int m,a,b,c;cou

15、t<<"请输入凸多边形顶点个数：”；cin»m;int M = m-1;for(i nt i=0 ; i<m ; i+)cout<<"输入顶点v"<<i<<"的坐标："cin> >vi.x»vi.y;/根据顶点坐标判断是否能构成一个凸多边形for(i nt 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

16、 * vm-1.x;elsea = vj.y - vj+1.y;b = vj.x - vj+1.x;c = b * vj.y - a * vj.x;for(i nt 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<<"无法构成凸多边形！"<<e ndl;exit(1);bool

17、mi nWeightTria ngulatio n()计算最优值算法int M;int *t, *s;point *v;for(i nt i=1 ; i<=M ; i+)tii = 0;for(i nt r=2 ; r<=M ; r+)for(i nt i=1 ; i<=M-r+1 ; i+)int j = i+r-1;tij = ti+1j + w(vi-1,vi,vj);sij = i;for(i nt k=i+1 ; k<i+r-1 ; k+)int u = tik + tk+1j + w(vi-1,vk,vj);if(u < 圳j)tij = u;sij

18、= k;return true; void Traceback(i nt i, i nt j, i nt *s)if(i = j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<"三角形：v"<<i-1<<"v"<<sij<<"v"<<j<<e ndl; int mai n()记录最优三角剖分中所有三角形信息记录最优三角剖分所对应的权函数值 记录凸多边形各顶点坐标记录坐标在直线方程中的值int

19、*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 in tN;si = new in tN;v = new poi ntN;total = new in tN;if(Judgel nput()if(mi nWeightTria ngulatio n()Traceback(1,M,s);cout<<e ndl;cout<<"最优权值之和为:return 0;运行结果:l'I I:MJScode

20、3.50边形最优三角剖分心e0122126慣输入凸级边形顶点个数=T 输入顶点询的坐标：8 26 输入顶点ML的坐标：0 20 輸入顶点说的坐标：0 10 输入顶点说的坐标：10 输入触点叽的坐棕：22 输入顶点诩的坐标：27 樹入顶点v6的坐标：15 二角形：v0vlv2 匚甬麻：v2v3v4 三角形：v0v2v4 巨角形：v4v5ir 二角形：v0v4v6 |最优和值之和为：22SProcess returned 0 (OjtO) execution time I 49965 s Press any key to continue.5、流水作业调度#in clude<iostream

21、>#defi ne N 100 using n amespace std;class Jobtypepublic:/* i nt operator<=(Jobtype a)c onstreturn(key<=a.key);*/int key;int in dex;bool job;； void sort(Jobtype *d,i nt n)int i,j;Jobtype temp;最多做n-1趟排序本趟排序开始前，交换标志应为假发生了交换，故将交换标志置为真本趟排序未发生交换，提前终止算法bool excha nge; /交换标志for(i = 0;i < n;i +)

22、 /excha nge = false; /for(j = n - 1;j >= i;j -) if(dj+1.key < dj.key) temp = dj+1;dj+1 = dj; dj = temp;excha nge=true; /if(!excha nge) /return;int FlowShop(i nt n,i nt *a,i nt *b,i nt *c)Jobtype *d = new Jobtype n;for(i nt i=0;i< n;i+)初始化执行时间di.key=ai>bi?bi:ai; di.job=ai<=bi;作业组di.i n

23、dex=i;作业序号sort(d, n);int j=0;int k=n-1;for(i nt i=0;i< n;i+)最优调度if(di.job)cj+=di.i ndex;elseck-=di.i ndex;j=acO;k=j+bcO;for(i nt i=1;i< n; i+)j+=aci; k=j<k?k+bci:j+bci;delete d;回收空间return k;返回调度时间int mai n()int n ,*a,*b,*c;cout<<"作业数："cin»n;Jobtype *d = new JobtypeN;a=n

24、ew in tN;b=new in tN;c=new in tN;cout<<"请输入作业号和时间："for(i nt i=0;i <n ;i+)cin> >di.i ndex»di.key;cout << en dl;int k=FlowShop( n, a,b,c);cout<<"n调度时间："<<k<<e ndl;输出最优调度序列cout<<" 最优调度序列:"for (int i = 0; i < n; i+)/cout

25、<< ci << ""return 0;运行结果:篡法code3.9流水作业调S.exe口 回 S3和时间:executron- tiiiLe ! 27.283 s调度时间：385319& 最优调度序列：2 3 0 1 Process returned 0 (0x0)Press any key to continue.6、0-1背包问题#in elude <iostream> #i nclude <ioma nip> using n amespace std;const int C=10;容量const int N=5

26、;个数int max(c onst int a,c onst int b) retur n a>b?a:b; int min(const int a,c onst int b) retur n a<b?a:b; /*m为记录数组mij代表在剩有j容量的条件下，从i开始往后的物品中可以取得的最大价值w为重量数组，v为价值数组n为物品个数，c为开始容量则m1c即此背包能剩下的最大价值*/void kn apsack(i nt *m,i nt n, int c,i nt *w, int *v)int jMax = min(wn-1,c);前 n-1 个物品for(i nt j=0;jv=

27、jMax;j+)m nj=0;for(i nt j=w n ;j<=c;j+)m nj=v n;for(i nt i=n-1;i>1;i-)jMax=mi n(wi-1,c);for(i nt j=O;jv=jMax;j+)mij = mi+1j;for(i nt 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(i nt *m,i nt n ,i nt c,i nt *x,i nt *

28、w) for(i nt i=1;i <n ;i+)if(mic=mi+1c) xi=0; elsexi=1;c-=wi;x n=(m nc=0)?0:1;int mai n()int *v=new in tN+1;int *w=new in tN+1;int *m=new in t* N+1;int *x=new in t N+1;for(i nt i=0;i<N+1;i+)mi=new in tC+1;coutvv"输入重量序列,"<<N<<"个"<<endl;for(i nt i=1;i<=N;i

29、+)ci n> >wi;cout«"输入价值序列,"<<N<<"个"<<endl;for(i nt i=1;i<=N;i+)cin> >vi;kn apsack(m,N,C,w,v);traceback(m,N,C,x,w);cout«"最优值："<<m1Cvvendl; coutvv"是否装入背包的情况："for(i nt i=1;i<=N;i+)cout<<xi;for(int i=0;i<

30、N+1;i+)delete mi;delete m;return 0;运行结果! 1 "l：W£code3,10| 口 | 回| S3输A重量序列/个俞入价值序列,5个3 4 2 7 1聶价值* id是否装入背包的情况；11010proc亡s凸 工亡turri亡d 0 （0x0）亡xacirtio垃血匚：IN 丁2吕 srrr7、最优二叉搜索树#in clude<iostream>#in clude<cmath>#i nclude<limits>#defi ne N 100using n amespace std;const double MAX = nu meric_limits<double>:max(); /double的最大值 ai为结点i被访问的概率bi为“虚结点” i被访问的概率/mij用来存放子树（i,j）的期望代价wij用来存放子树（i,j）的所有结点（包括虚结点）的 a,b概率之和/sij用来跟踪root的void Opt