算法回溯递归动态贪心分支综合代码

1、/3d1-2 矩阵连乘 动态规划迭代实现/A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25/p0-6=30,35,15,5,10,20,25/#include <stdafx.h>#include <iostream> using namespace std; const int L = 7;int MatrixChain(int n,int *m,int *s,int *p); void Traceback(int i,int j,int *s);/构造最优解int main()int pL=30,35,15,5,

2、10,20,25; int *s = new int *L;int *m = new int *L;for(int i=0;i<L;i+) si = new intL;mi = new intL; cout<<"矩阵的最少计算次数为："<<MatrixChain(6,m,s,p)<<endl;cout<<"矩阵最优计算次序为："<<endl;Traceback(1,6,s);return 0;int MatrixChain(int n,int *m,int *s,int *p)for(in

3、t i=1; i<=n; i+)mii = 0;for(int r=2; r<=n; r+) /r为当前计算的链长（子问题规模） for(int i=1; i<=n-r+1; i+)/n-r+1为最后一个r链的前边界 int j = i+r-1;/计算前边界为r，链长为r的链的后边界 mij = mi+1j + pi-1*pi*pj;/将链ij划分为A(i) * ( Ai+1:j ) sij = i;for(int k=i+1; k<j; k+)/将链ij划分为( Ai:k )* (Ak+1:j) int t = mik + mk+1j + pi-1*pk*pj;if(

4、t<mij)mij = t;sij = k;return m1L-1;void Traceback(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<"Multiply A"<<i<<","<<sij;cout<<" and A"<<(sij+1)<<","<<j<<endl;#include

5、<stdio.h>#include <string>#include<iostream>using namespace std;string pre,post;/确定的先后序/已知中序和后序确定先序void Preorder(string a, string b)/a中序b后序int r=a.find(b.substr(b.length()-1,1);/在后序中找根节点pre+=ar;if(r>0)Preorder(a.substr(0,r),b.substr(0,r);if(r<a.length()-1) Preorder(a.substr(r

6、+1, a.length()-r-1), b.substr(r, b.length()-r-1);/递归分割/已知先序和中序确定后序void Postorder(string a, string b)/a中序b先序int r=a.find(b.substr(0,1);/在前序中找根节点if(r>0)Postorder(a.substr(0,r),b.substr(1,r);if(r<a.length()-1) Postorder(a.substr(r+1, a.length()-r-1), b.substr(r+1, b.length()-r-1);/递归分割post+=ar;vo

7、id main()while(true)int choice = 0;string p1,p2;cout<<" 输入选择：(数字) "<<endl;cout<<" 1.已知后序和中序序列,求先序序列： "<<endl;cout<<" 2.已知先序和中序序列,求后序序列： "<<endl;cout<<" 3.退出 "<<endl;cin>>choice;switch(choice)case 1:cout<

8、<"输入中序序列："<<endl;cin>>p1;cout<<"输入后序序列："<<endl;cin>>p2;Preorder(p1,p2);cout<<"唯一的先序序列是："<<endl;cout<<pre<<endl;break;case 2:cout<<"请输入先序序列："<<endl;cin>>p2;cout<<"请输入中序序列：&quo

9、t;<<endl;cin>>p1;Postorder(p1,p2);cout<<"后序序列为："<<endl;cout<<post<<endl;break;case 3:return;default:cout<<"输入错误，请重新输入数字"<<endl;return ;/(动态规划)01背包#include <stdio.h> #include <tchar.h> #include <queue> #include &quo

10、t;iostream" using namespace std; const int N = 4; /物品个数n为3const int W = 6; /总重量w为6int weightN = 0,4,3,2; int valueN = 0,5,2,1; int recordN7; int xN;void init() for(int i = 0; i <N; i +) for(int j = 0; j < W; j +) recordij = -1; int min(int x,int y)int u;if(x<=y)u=x;elseu=y;return u;int

11、 max(int x,int y)int u;if(x>=y)u=x;elseu=y;return u;void Knapsack(int* v,int* w,int c,int n,int m7)int jMax=min(wn-1,c);/第n个物品for(int j=0;j<=jMax;j+)/cout<<n<<" "<<j<<endl;mnj=0;/cout<<mnj<<endl;for(j=wn;j<=c;j+)/cout<<n<<" &quo

12、t;<<j<<endl;mnj=vn;/cout<<mnj<<endl;for(int i=n-1;i>1;i-)/第i个物品jMax=min(wi-1,c);for(int j=0;j<=jMax;j+)mij=mi+1j;for(j=wi;j<=c;j+)mij=max(mi+1j,mi+1j-wi+vi);/cout<<m2c<<endl;m1c=m2c;/第一个物品/cout<<m1c<<endl;if(c>=w1)m1c=max(m2c,m2c-w1+v1);/co

13、ut<<c<<" "<<m1c<<endl;for(i=1;i<=n;i+)cout<<"第"<<i<<"个物品值： "for(j=0;j<=6;j+)cout<<mij<<" "cout<<endl;cout<<endl;void Traceback(int m7,int* w,int c,int n,int* x)for(int i=1;i<n;i+)if(mic

14、=mi+1c)xi=0;else xi=1;c-=wi;xn=(mnc)?1:0;for(i=1;i<=n;i+)cout<<"第"<<i<<"号物品的值为："<<xi<<endl;cout<<endl; int main() init(); Knapsack(value,weight,W,3,record); Traceback(record,weight,W,3,x); return 0; /(动态规划)公共子序列#include <stdio.h>#inclu

15、de <string.h>#define MAXLEN 100void LCSLength(char *x, char *y, int m, int n, int cMAXLEN, int bMAXLEN) int i, j; for(i = 0; i <= m; i+) ci0 = 0; for(j = 1; j <= n; j+) c0j = 0; for(i = 1; i<= m; i+) for(j = 1; j <= n; j+) if(xi-1 = yj-1) cij = ci-1j-1 + 1; bij = 0; else if(ci-1j &

16、gt;= cij-1) cij = ci-1j; bij = 1; else cij = cij-1; bij = -1; void PrintLCS(int bMAXLEN, char *x, int i, int j) if(i = 0 | j = 0) return; if(bij = 0) PrintLCS(b, x, i-1, j-1); printf("%c ", xi-1); else if(bij = 1) PrintLCS(b, x, i-1, j); else PrintLCS(b, x, i, j-1);int main(int argc, char

17、*argv) char xMAXLEN = "ABCBDAB" char yMAXLEN = "BDCABA" int bMAXLENMAXLEN; int cMAXLENMAXLEN; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); PrintLCS(b, x, m, n); return 0;/（动态规划）矩阵连乘#include <iostream> using namespace std; const int W= 7;/矩阵连乘 int Mat

18、rixChain(int *p,int n,int *m,int *s)/动态规划迭代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;return m1W-1;void Traceback(int

19、i,int j,int *s)/构造最优解if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<"Multiply A"<<i<<","<<sij;cout<<" and A"<<(sij+1)<<","<<j<<endl;int main()int pW=30,35,15,5,10,20,25; int *s = new int *W;in

20、t *m = new int *W;for(int i=0;i<W;i+) si = new intW;mi = new intW; cout<<"矩阵最少计算次数为："<<MatrixChain(p,6,m,s)<<endl;cout<<"矩阵最优计算次序为："<<endl;Traceback(1,6,s);return 0;/（分支限界）01背包#include<iostream> #include<stack> using namespace std;#def

21、ine N 50double wN,pN; /把物品重量和价值定义为双精度浮点数 double cw,cp,c; /cw为当前重量，cp为当前价值，背包容量 int n; /货物数量为3 class HeapNode /定义HeapNode结点类 public: double uprofit; /uprofit为结点的价值上界double profit;/profit是结点所对应的价值double weight;/weight为结点所相应的重量 int level;/活节点在子集树中所处的层序号int ptrN; ; stack<HeapNode> hnode; double Ma

22、xBound(int j) /结算结点相应价值的上界 double left=c-cw; /剩余容量 double b=cp; /价值上界 /以物品单位重量价值递减装填剩余容量 while(j<=n&&wj<=left) left-=wj; b+=pj; j+; /装填剩余容量装满背包 if(j<=n) b+=pj/wj*left; return b; /将一个新的活结点插入到子集树和堆hnode中 void AddLiveNode(double up,double cp,double cw,bool ch,int lev) HeapNode tnode; t

23、node.uprofit=up; fit=cp; tnode.weight=cw; tnode.level=lev; if(lev<=n) hnode.push(tnode); double Knap() /优先队列分支限界法，返回最大价值，bestx返回最优解 int i=1;cw=cp=0; double bestp=0,up=MaxBound(1); /计算价值上界 while(true) double wt=cw+wi; if(wt<=c) /左儿子结点为可行结点 if(cp+pi>bestp)bestp=cp+pi;AddLiveNode(up,c

24、p+pi,cw+wi,true,i+1);up=MaxBound(i+1);/检查当前扩展结点的左儿子结点if(up>=bestp) /右子数可能含最优解 AddLiveNode(up,cp,cw,false,i+1);if(hnode.empty() return bestp; /取下一扩展结点 HeapNode node=hnode.top(); hnode.pop(); cw=node.weight;cp=fit;up=node.uprofit; i=node.level; int main() cout<<"请输入物品个数："<

25、;<endl;cin>>n;cout<<"请输入每个物品的重量："<<endl; for(int i=1;i<=n;i+) cin>>wi; cout<<"请输入每个物品的价值："<<endl; for(i=1;i<=n;i+) cin>>pi; cout<<"输入背包容量："<<endl;cin>>c;cout<<"最大价值为：" cout<<Knap(

26、)<<endl;return 0; /分支限界法批处理调度问题#include<iostream>#include<queue> using namespace std;class MinHeapNode friend class Flowshop; public: bool operator<(const MinHeapNode &a)constreturn a.bb<bb; private: void Init(int),NewNode(MinHeapNode,int,int,int,int); int s; /已安排作业数 int

27、f1; /机器1上最后完成时间 int f2; /机器2上最后完成时间 int sf2; /当前机器2上的完成时间和 int bb; /当前完成时间和下界 int *x; /当前作业调度 ; void MinHeapNode:Init(int n) /最小堆结点初始化 x=new intn; for(int i=0;i<n;i+) xi=i; s=0; f1=0; f2=0; sf2=0; bb=0; void MinHeapNode:NewNode(MinHeapNode E,int Ef1,int Ef2,int Ebb,int n) /最小堆新结点 x=new intn; for(

28、int i=0;i<n;i+) xi=E.xi; f1=Ef1; f2=Ef2; sf2=E.sf2+f2; bb=Ebb; s=E.s+1; class Flowshop friend int main(); public: int BBFlow(); private: Flowshop(int n); Flowshop(); int Bound(MinHeapNode,int &,int &,bool *); void Sort(); int n;/作业数 int *M; /各作业所需处理时间数组 int *b; /各作业所需处理时间排序数组 int *a; /数组M

29、（在主函初始化）和b对应关系数组 int *bestx; /最优解 int bestc; /最小完成时间 bool *y; /工作数组 ; Flowshop:Flowshop(int n) /初始化 b=new int *n; a=new int *n; y=new bool *n; bestx=new int n; bestc=2000; for(int i=0;i<n;i+) bi=new int2; ai=new int2; yi=new bool2; Flowshop:Flowshop() for(int i=0;i<n;i+) delete Mi; delete bi;

30、delete ai; delete yi; delete bestx,M,b,a,y; void Flowshop:Sort() /对各作业在机器1和2上所需时间排序 int *c=new intn; for(int j=0;j<2;j+) for(int i=0;i<n;i+) bij=Mij; ci=i; for(i=0;i<n-1;i+) for(int k=n-1;k>i;k-) if(bkj<bk-1j) swap(bkj,bk-1j); swap(ck,ck-1); for(i=0;i<n;i+) acij=i; delete c; int Fl

31、owshop:Bound(MinHeapNode E,int &f1,int &f2,bool *y) /计算完成时间和下界 for(int k=0;k<n;k+) for(int j=0;j<2;j+) ykj=0; for(k=0;k<=E.s;k+) for(int j=0;j<2;j+) yaE.xkjj=1; f1=E.f1+ME.xE.s0; f2=(f1>E.f2)?f1:E.f2)+ME.xE.s1; int sf2=E.sf2+f2; int s1=0,s2=0,k1=n-E.s,k2=n-E.s,f3=f2; /计算s1的值 f

32、or(int j=0;j<n;j+) if(!yj0) k1-; if(k1=n-E.s-1) f3=(f2>f1+bj0)?f2:f1+bj0; s1+=f1+k1*bj0; /计算s2的值 for(j=0;j<n;j+) if(!yj1) k2-; s1+=bj1; s2+=f3+k2*bj1; /返回完成时间和下界 return sf2+(s1>s2)?s1:s2); int Flowshop:BBFlow() /解批处理作业问题调度问题的优先队列式分支限界法Sort(); /对各作业在机器1和2上所需时间排序priority_queue<MinHeapNo

33、de> H; MinHeapNode E; /初始化E.Init(n);/搜索排列空间树while(E.s<=n) if(E.s=n)/叶节点 if(E.sf2<bestc) bestc=E.sf2; for(int i=0;i<n;i+) bestxi=E.xi; delete E.x; else /产生当前扩展节点的儿子节点for(int i=E.s;i<n;i+) swap(E.xE.s,E.xi); int f1,f2; int bb=Bound(E,f1,f2,y); if(bb<bestc) MinHeapNode N; N.NewNode(E,

34、f1,f2,bb,n); H.push(N); swap(E.xE.s,E.xi); delete E.x; if(H.empty() break; else E=H.top(); H.pop(); return bestc; int main() int n=3; int *M = new int*3; for(int i=0; i<=2; +i) Mi = new int2; M00 = 2; M01=1; M10 = 3; M11=1; M20 = 2; M21=3; cout<<" Tji | 机器1 | 机器2 "<<endl; co

35、ut<<"-"<<endl; for(int m=0; m<=2; m+) cout<<"作业"<<m<<" | " for(int n=0; n<=1; n+) cout<< Mmn << " | " cout << endl; Flowshop G(n); G.M=M; G.n=n; int f=G.BBFlow(); cout<<"最佳调度方案是:" for(i=0;i&

36、lt;n;i+) cout<<G.bestxi+1<<" " cout<<endl; cout<<"其完成时间和:"<<f<<endl; return 0; /分治棋盘#include <stdio.h>#define MAX 100int boardMAXMAX ;/棋盘int tile = 0 ;/棋盘覆盖void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; in

37、t t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖右上角子棋盘 if (dr < tr + s && dc >

38、;= tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角 boardtr + s - 1tc + s = t; /棋盘覆盖（续） / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else / 用 t 号L型骨牌覆盖右上角 b

39、oardtr + stc + s - 1 = t; / 覆盖其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s); / 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上角 boardtr + stc + s = t; / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); bool validate(int n)if(n =

40、1)return false;while(n / 2 > 0)if(n % 2 != 0)return false;n /= 2;return true;int main()int dr, dc, tr, tc, size;/drdc特殊方格的位置，trtc棋盘左上角的位置int i ,j;dr = 0;dc = 2;tr = 0;tc = 0;printf("输入棋盘大小:");/size=2k，规格为2k*2kscanf("%d", &size);while(!validate(size)printf("大小必须为2的n次方，

41、请重新输入n");scanf("%d", &size);printf("输入特殊方格的位置");scanf("%d%d", &dr, &dc);chessBoard(tr, tc , dr , dc , size);/打印for(i = 0 ; i < size ; i+)for(j = 0 ; j < size; j+)if(i = dr && j = dc)/打印特殊方格printf(" * ");elseprintf("%3d "

42、;,boardij);printf("n");return 0;/分治循环赛日程表#include<stdio.h>#include<malloc.h>#define MAXSIZE 50;int * a;void init(int n)a = (int *)malloc( (n+1) * sizeof(int *);for( int i = 0 ; i <= n + 1 ; i+)ai = (int *)malloc(n+1) * sizeof(*a);for( i = 1 ; i <= n ; i+)for(int j = 1 ; j

43、 <= n ; j+)aij = 0;void Table(int k,int * a)/循环赛日程表分治算法int n=1;int i , j , s , t ;for(i=1; i <= k; i +) n*=2;for(i=1; i <= n; i +) a1i=i;int m=1;for(s = 1 ; s <= k ; s+)n /= 2;for(t = 1 ; t <= n ; t+)for(i = m + 1 ; i <= 2 * m ; i+)for(j = m + 1 ; j <= 2 * m ; j+)aij + (t - 1) *

44、 m * 2 = ai - m j + (t - 1) * m * 2 - m;aij + (t - 1) * m * 2 - m = ai - m j + (t - 1) * m * 2 ;m *= 2;int main()int k , n = 1;int i=1 , j;printf("请输入n个运动员的2的幂n");scanf("%d",&k);/n=2kwhile(i<=k)/计算有多少个运动员n*=2;i+;init(n);Table(k,a);/打印输出for( i = 1 ; i <= n ; i+)for(j = 1

45、 ; j <= n ; j+)printf("%2d ",aij);printf("n");return 0;/回溯01背包#include <stdio.h>int n;/物品数int id10;/物品编号float c;/背包容量float v10;/物品价值数组float w10;/物品重量数组float cw = 0.0;/当前重量float cp = 0.0;/当前价值float bestp = 0.0;/当前最优价值float perv10;/单位物品价值排序的数组bool isPuting10;/物品是否装入void So

46、rt() int i,j; int tempId = 0; float temp = 0.0; for(i=1;i<=n;i+) pervi=vi/wi;/计算单位重量价值 for(i=1;i<=n-1;i+)/单位重量价值降序排序 for(j=i+1;j<=n;j+) if(pervi<pervj) tempId=idi; idi=idj; idj=tempId; temp = pervi; pervi=pervi; pervj=temp; temp = vi; vi=vj; vj=temp; temp=wi; wi=wj; wj=temp; /*for(i=1;i&

47、lt;n;i+)printf("%.2f ",pervi);*/printf("n");float Bound(int i)/计算上界 float cleft= c-cw;/当前剩余容量 float b = cp; while(i<=n&&wi<=cleft) cleft-=wi; b+=vi; i+; if(i<=n) b+=vi/wi*cleft; return b;/回溯函数void BackTrack(int i) float Bound(int i); if(i>n)/到达叶子节点 bestp = cp; return; if(cw+wi<=c)/进入左子树 cw+=wi; cp+=vi; isPutingi=1; BackTrack(i+1); cw-=wi; cp-=vi; if(Bound(i+1)>bestp)/进入右子树 Ba