動態(tài)規(guī)劃算法試驗報告材料

1、實用標(biāo)準(zhǔn)文檔文案大全實驗標(biāo)題實驗?zāi)康膶嶒瀮?nèi)容與源碼1、矩陣連乘2 、最長公共子序列 3 、最大子段和4、凸多邊形最優(yōu)三角剖分5 、流水作業(yè)調(diào)度6、 0-1 背包問題7 、最優(yōu)二叉搜索樹掌握動態(tài)規(guī)劃法的基本思想和算法設(shè)計的基本步驟。1、矩陣連乘#include<iostream> #include<cstdlib> using namespace std;const int size=4;ra,ca和rb,cb分別表示矩陣 A和B的行數(shù)和列數(shù)void matriMultiply(inta4,int b4,int c4,int ra ,int ca,intrb ,int c

2、b )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; m

3、ij=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<<")"elsecout<<&

4、quot;("Traceback(i,sij,s);Traceback(sij+1,j,s); cout<<")"int main()int w;cout<<" 矩陣個數(shù)： "cin>>w;int pw,sww;cout<<" 輸入矩陣 A1 維數(shù)： " cin>>p0>>p1;for(int i=2 ; i<=w ; i+)int m = pi-1;cout<<" 輸入矩陣 A"<<i<<&

5、quot; 維數(shù)： " cin>>pi-1>>pi;if(pi-1 != m)"<<endl;cout<<endl<<" 維數(shù)不對，矩陣不可乘！ exit(1);Traceback(1,w,s);return 0;運行結(jié)果2、最長公共子序列#in clude<cstri ng>#in clude<iostream>#defi ne N 100using n amespace std;str1存儲字符串x, str2存儲字符串ychar str1N,str2N;/lcs存儲最長公共子

6、序列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(i=1;i<=m;i+) ci0 = 0;for(i=0;i<=n ;i+) c0i = 0;for(i=1;i&l

7、t;=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 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-

8、;j-;else if(flagij=1)i-;elsej-;return lcs;int main()int i;cout<<" 請輸入字符串 x： "<<endl;cin>>str1;cout<<"請輸入字符串y： "<<endl;cin> >str2;in t IcsLe n = LCSLe ngth(str1,str2);cout<<"最長公共子序列長度："<<lcsLe n<<endl;char *p = getLCS

9、(str1,str2,lcsLe n,lcs);cout<<"最長公共子序列為："for(i=0;i<lcsLe n;i+) cout<<lcsi<<""return 0;運行結(jié)果3、最大子段和 /分治法求最大子段和#in clude<iostream> 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

10、= (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>=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)

11、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;/ 動態(tài)規(guī)劃法 #include<iostream> u

12、sing 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 mai n()int a8=2,-3,-5,4,1,7,1,-5;cout<<"最大子段和為："<<MaxSum(a,8); return 0;運行結(jié)果4、凸多邊形最優(yōu)三角剖分#in clude<iostream>#in clude

13、<cmath>#in clude<cstdlib>#defi ne N 50using n amespace std;struct pointint x;int 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)/權(quán)值retur n dista nce(a,b) + dista nce(b,c) + dista nce(a,c)

14、; 判斷是否能構(gòu)成凸多邊形point *v;/bool Judge In put()int *total;/記錄凸多邊形各頂點坐標(biāo)記錄坐標(biāo)在直線方程中的值int m,a,b,c;cout<<" 請輸入凸多邊形頂點個數(shù)： " cin>>m;int M = m-1;for(int i=0 ; i<m ; i+)cout<<" 輸入頂點 v"<<i<<" 的坐標(biāo)： " cin>>vi.x>>vi.y;/ 根據(jù)頂點坐標(biāo)判斷是否能構(gòu)成一個凸多邊形 for(

15、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;elsea = 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

16、>0 && q>0) | (p=0 && q=0)cout<<" 無法構(gòu)成凸多邊形！ "<<endl; exit(1);bool minWeightTriangulation()/ 計算最優(yōu)值算法 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,

17、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<&l

18、t;"v"<<j<<endl; int main()記錄最優(yōu)三角剖分中所有三角形信息 記錄最優(yōu)三角剖分所對應(yīng)的權(quán)函數(shù)值 記錄凸多邊形各頂點坐標(biāo) 記錄坐標(biāo)在直線方程中的值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 in tN;si = new in tN;v = new poi ntN;total = new in tN;if(Judgel nput()if(mi nWeigh

19、tTria ngulatio n()Traceback(1,M,s);cout<<e ndl;cout<<"最優(yōu)權(quán)值之和為："<<t1M<<e ndl;return 0;運行結(jié)果：5、流水作業(yè)調(diào)度#in clude<iostream>#defi ne N 100using n amespace std;class Jobtypepublic:/* i nt operator<=(Jobtype a)c onstreturn(key<=a.key);*/int key;int index;bool job

20、;void sort(Jobtype *d,int n) int i,j;Jobtype temp;bool exchange; /交換標(biāo)志最多做 n-1 趟排序本趟排序開始前，交換標(biāo)志應(yīng)為假發(fā)生了交換，故將交換標(biāo)志置為真本趟排序未發(fā)生交換，提前終止算法for(i = 0;i < n;i +) /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;i

21、nt FlowShop(int n,int *a,int *b,int *c)Jobtype *d = new Jobtypen;for(int i=0;i<n;i+)/ 初始化執(zhí)行時間di.key=ai>bi?bi:ai;/ di.job=ai<=bi;/ 作業(yè)組 di.index=i;/ 作業(yè)序號sort(d,n);int j=0;int k=n-1;for(int i=0;i<n;i+)/ 最優(yōu)調(diào)度if(di.job)cj+=di.index; elseck-=di.index;j=ac0;k=j+bc0;for(int i=1;i<n;i+)j+=aci;

22、k=j<k?k+bci:j+bci;delete d;/回收空間return k;/返回調(diào)度時間int main()int n,*a,*b,*c;cout<<" 作業(yè)數(shù)： "cin>>n;Jobtype *d = new JobtypeN;a=new intN;b=new intN;c=new intN;cout<<" 請輸入作業(yè)號和時間： "for(int i=0;i<n;i+)cin>>di.index>>di.key;cout << endl;int k=FlowS

23、hop(n,a,b,c);cout<<"n 調(diào)度時間： "<<k<<endl;輸出最優(yōu)調(diào)度序列cout<<" 最優(yōu)調(diào)度序列 :"for (int i = 0; i < n; i+)/cout << ci << " "return 0;運行結(jié)果：* I:fi;ScQde3.9流水作業(yè)調(diào)S.exe非業(yè)數(shù)；4請輸入作業(yè)號和時間;0 91 222 63 76、0-1背包問題#in elude <iostream> #i nclude <ioma n

24、ip> using n amespace std;const int C=10;容量const int N=5;個數(shù) 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為記錄數(shù)組mij代表在剩有j容量的條件下，從i開始往后的物品中可以取得的最大價值w為重量數(shù)組，v為價值數(shù)組n為物品個數(shù)，c為開始容量則m1c即此背包能剩下的最大價值*/void kn apsack(i nt *m,i nt n, int c,i nt

25、*w, int *v)int jMax = min(wn-1,c);前 n-1 個物品for(i nt j=0;jv=jMax;j+)m nj=0;for(i nt j=w n ;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);/ 找出最優(yōu)解， 0表示不能裝，

26、 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;elsexi=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<<

27、" 個 "<<endl; for(int i=1;i<=N;i+)cin>>wi;cout<<" 輸入價值序列 ,"<<N<<" 個 "<<endl; for(int i=1;i<=N;i+)cin> >vi;kn apsack(m,N,C,w,v); traceback(m,N,C,x,w);cout«"最優(yōu)值："<<m1Cvvendl; coutvv"是否裝入背包的情況："f

28、or(i nt i=1;i<=N;i+)cout<<xi;for(int i=0;i<N+1;i+)delete mi;delete m;return 0;運行結(jié)果7、最優(yōu)二叉搜索樹#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為結(jié)點i被訪問的概率bi為“虛結(jié)點” i被訪問的概率/mij用來存放子樹（i,j）的期望代價wij用來存放子樹（i,j）的所有結(jié)點（包括虛結(jié)點）的 a,b概率之和/sij用來跟蹤root的void OptimalB in arySearchTree(double *a,double *b,i nt n)int sNN;double mNN;double wNN;in