算法设计与分析书中程序(第07章)

《算法设计与分析书中程序(第07章)》由会员分享，可在线阅读，更多相关《算法设计与分析书中程序(第07章)（9页珍藏版）》请在装配图网上搜索。

1、 【程序7-1】 多段图的向前递推算法templateT Graph:FMultiGraph(int k, int *p)/采用程序6-8的邻接表存储图GTc,*cost=new floatn; int q, *d=new intn;costn-1=0, dn-1= -1;/设置向前递推的初值for (int j=n-2; j=0; j-)/按n-2, , 0的次序计算cost和dfloat min=INFTY;/按式（7-1）计算最小值为costjfor (ENode *r=aj; r; r=r-nextArc) int v=r-adjVex;if (r-w+costvw+costv; q=

2、v;costj=min; dj=q;/q是j在最短子路径上的后继结点p0=0; pk-1=n-1; c=cost0;/p0和pn-1是源点和汇点for(j=1; j=k-2; j+) pj=dpj-1;/pi是最短路径上第i阶段的结点delete cost; delete d; return c; 【程序7-2】 弗洛伊德算法templatevoid MGraph:Floyd(T*& d, int *& path)int i, j, k;d= new T*n; path=new int *n;for(i=0; in; i+)di=new T n; pathi=new intn;for (j=0

3、; jn; j+)/初始化dij=aij;if (i！=j & wijINFTY) pathij=i;else pathij= -1;for (k=0; kn; k+)/考察结点kfor (i=0; in; i+)for (j=0; jn; j+) if (dik+dkj dij )dij=dik+dkj;pathij=pathkj; 【程序7-3】 矩阵连乘算法class MatrixChainpublic:MatrixChain(int mSize, int *q);/创建二维数组m和s，一维数组p，并初始化int MChain();/一般动态规划法求最优解值int LookupChain

4、();/备忘录方法求最优解值（程序7-4）void Traceback();/构造最优解的公有函数private:void Traceback(int i, int j);/构造最优解的私有递归函数int LookupChain(int i, int j);/备忘录方法私有递归（程序7-4）int *p, *m, *s, n;int MatrixChain:MChain() /求A0:n-1的最优解值for (int i=0;in; i+) mii=0;for (int r=2; r=n; r+)for (int i=0; i=n-r; i+) int j=i+r-1;mij=mi+1j+pi

5、*pi+1*pj+1; /mij 的初值sij=i;for (int k=i+1; kj; k+) int t=mik+mk+1j+pi*pk+1*pj+1;if (tmij) mij=t; sij=k;return m0n-1;void MatrixChain:Traceback(int i, int j)if(i=j) coutAi; return;if (isij) cout(; Traceback(i, sij); if (isij)cout);if(sij+1j)cout(; Traceback(sij+1, j); if(sij+1j) cout);void MatrixChain

6、:Traceback()cout(; Traceback(0, n-1); cout);cout0) return mij;/子问题已经求解，直接引用if(i=j) return 0;/单一矩阵无须计算int u=LookupChain(i+1, j)+pi*pi+1*pj+1;/按式（7-9）求最小值sij=i;for (int k=i+1; kj; k+) int t=LookupChain(i, k)+LookupChain(k+1, j)+pi*pk+1*pj+1;if (tu) u=t; sij=k;mij=u; return u;/保存并返回子最优解值int MatrixChain

7、:LookupChain()return LookupChain(0, n-1); /返回A0:n-1的最优解值 【程序7-5】 求LCS的长度class LCSpublic:LCS(int nx, int ny, char *x, char*y);/创建二维数组c、s和一维数组a、b，并进行初始化void LCSLength();/求最优解值（最长公共子序列长度）void CLCS();/构造最优解（最长公共子序列）private:void CLCS(int i, int j);int *c, *s.m, n;char *a, *b;int LCS:LCSLength() for(int i

8、=1; i=m; i+) ci0=0; for(i=1; i=n; i+) c0i=0;for (i=1; i=m; i+)for (int j=1; j=cij-1)cij=ci-1j; sij=2;/由ci-1j得到cijelse cij=cij-1; sij=3;/由cij-1得到cijreturn cmn;/返回最优解值 【程序7-6】 构造最长公共子序列void LCS:CLCS(int i, int j)if (i=0|j=0) return;if (sij=1)CLCS(i-1, j-1);coutai;else if (sij=2) CLCS(i-1, j); else CLC

9、S(i, j-1); 【程序7-7】 构造最优二叉搜索树int Find(int i, int j, int *r, float*c)float min=INFTY; int k;for (int m=i+1; m=j; m+)if (cim-1+cmj)min) min=cim-1+cmj; k=m;return k;void CreateOBST(float* p, float* q, float *c, int *r, float*w, int n)for (int i=0; i=n-1; i+) /初始化wii=qi; cii=0.0; rii=0;wii+1=qi+qi+1+pi+1

10、;cii+1=qi+qi+1+pi+1;rii+1=i+1;wnn=qn; cnn=0.0; rnn=0; for (int m=2; m=n; m+)/计算n-2条对角线元素 for (i=0; i=n-m; i+) int j=i+m;wij=wij-1+pj+qj;int k = Find(i, j, r, c);cij = wij + cik-1 + ckj;rij = k; 【程序7-8】 0/1背包的递归算法templateclass Knapsack public:Knapsack(int mSize, float cap, float *wei, T *prof); T RKn

11、ap();private:T f(int j, float X); float m, *w;T *p; int n;templateT Knapsack:f(int j, float X) if (j0) return (X0) ？-INFTY: 0); if (Xb)return a; else return b; templateT Knapsack: RKnap()if(n0) return f(n-1, m);else return NoAns;/NoAns可定义为类型T的一个代表无收益的常量【程序7-9】 0/1背包算法的粗略描述void DKP(float *p, float *w

12、, int n, float M, float &P, int *x)S-1=(0, 0);for (i=0; in-1; i+) =(X, P)|(X-wi, P-pi)Si-1 and XM; Si=MergerPurge(Si-1,);/合并两集合，并从中舍弃应去除的阶跃点(X1, P1)=Sn-2中最后一个阶跃点;(X2, P2)=(X+wn-1, P+pn-1)，其中(X, P)是Sn-1中使得X+wn-1M的最大的阶跃点;P=maxP1, P2;/P为最优解值If (P2P1) xn-1=1; else xn-1=0;回溯确定xn-2, xn-3, , x0;【程序7-10】 0/

13、1背包最优解值算法struct XP float X, P; templateclass Knapsack public:Knapsack(int sz, float cap, float *wei, T *prof); T DKnap(int *x); private: T DKnap(); void TraceBack(int*x); int Largest(int low, int high, int i); float m, *w; XP *p; T *pf; int n, *b;templateint Knapsack:Largest(int low, int high, int i

14、)int u=low-1;for (int j=low; j=high; j+) float ww=pj.X+wi; if(ww=m) u=j; return u;templateT Knapsack: DKnap() float ww, pp;int next; b0=0;p0.X=p0.P=0.0; p1.X=w0; p1.P=pf0;/S0int low=0, high=1;/S0的起止位置b1=next=2;/数组p的下一个空闲位置for (int i=1; i=n-1; i+) /由Si-1产生Si int k=low; int u=Largest(low, high, i); fo

15、r (int j=low; j=u; j+) /从Si-1生成，并合并成Si ww=pj.X+wi; pp=pj.P+pfi;/生成中的一个阶跃点(ww, pp) while (k=high) & (pk.Xww) /复制Si-1中的部分阶跃点到Si中 pnext.X=pk.X; pnext+.P=pk+.P; if (k=high & pk.X=ww) if (pppnext-1.P) /若(ww, pp)不被支配，则加入Si中 pnext.X=ww; pnext+.P=pp; while (k=high & pk.P=pnext-1.P) k+;/舍弃所有被支配的阶跃点 while (k=

16、high)/复制Si-1中剩余阶跃点到Si中 pnext.X=pk.X; pnext+.P=pk+.P; low=high+1; high=next-1; bi+1=next;/Si+1的初始化 return pnext-1.P ;/返回最大收益【程序7-11】 0/1背包最优解算法templatevoid Knapsack: TraceBack(int*x ) float ww=pbn -1.X;for (int j=n-1; j0; j-)xj=1;for (int k=bj-1; kbj; k+)if(ww=pk.X) xj=0; if(xj) ww=ww-wj;if(ww=0) x0=

17、0; else x0=1;【程序712】Johnson算法struct Triplet /三元组结构int operator (Triplet b)const return tb.t;int jobNo,t,ab; /jobNo为作业号，t为处理时间，ab为设备号;void FlowShop(int n, int *a,int *b,int *c) Triplet dmSize=0,0,0;for(int i=0;in;i+) /算法步骤（1）生成三元组表dif(aibi) di.jobNo=i;di.ab=0;di.t=ai;else di.jobNo=i;di.ab=1;di.t=bi;Sort(d,n); /算法步骤（2），任意排序算法int left=0,right=n-1;for (i=0;in;i+) /算法步骤（3），生成最优解if(di.ab=0) cleft+=di.jobNo;else cright-=di.jobNo;