5.回溯算法

装载问题：

问题描述：

有一批共n个集装箱要装上载重量为c的轮船，其中集装箱i重量为wi，集装箱装载问题要求确定在不超过轮船载重量的前提下，将尽可能多的集装箱装上轮船，且集装箱的重量之和最大

回溯算法实现：

#include<iostream> using namespace std; #define NUM 1000 int n; int c; int w[NUM]; int x[NUM]; int r; int cw; int bestw; int bestx[NUM]; void Backtrack(int t) { if(t>n) { if(cw>bestw) { for(int i=1; i<=n; i++) bestx[i] = x[i]; bestw = cw; } return; } r -= w[t]; if(cw+w[t]<=c) { x[t] = 1; cw += w[t]; Backtrack(t+1); cw -= w[t]; } if(cw+r>bestw) { x[t]=0; Backtrack(t+1); } r += w[t]; } int main() { while (scanf("%d%d", &c, &n)!=EOF) { r = 0; for(int i=1;i<=n;i++) { scanf("%d", &w[i]); r += w[i]; } cw = 0; bestw = 0; Backtrack(1); printf("%d\n", bestw); for(int i=1;i<=n;i++) if (bestx[i]) printf("%d ", i); printf("\n"); } }

0-1背包问题：

#include<iostream> using namespace std; #define NUM 100 int c; int n; int cw; int cv; int bestv; struct Object{ int w; int v; double d; }Q[NUM]; bool cmp(Object a, Object b) { if(a.d>=b.d) return true; else return false; } int Bound(int i) { int cleft = c-cw; int b = cv; while (i<n && Q[i].w<=cleft) { cleft -= Q[i].w; b += Q[i].v; i++; } if (i<n) b += cleft*Q[i].d; return b; } void backtrack(int i) { if (i+1>n) {bestv = cv; return;} if (cw+Q[i].w<=c) { cw += Q[i].w; cv += Q[i].v; backtrack(i+1); cw -= Q[i].w; cv -= Q[i].v; } if (Bound(i+1)>bestv) backtrack(i+1); } int main() { while(scanf("%d",&c) && c) { cw = 0; cv = 0; bestv = 0; scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d%d",&Q[i].w,&Q[i].v); Q[i].d = 1.0*Q[i].v/Q[i].w; } sort(Q, Q+n, cmp); backtrack(0); printf("%d\n", bestv); } return 0; }

图的m着色问题：

#include <iostream> using namespace std; #define NUM 100 int n; int m; int a[NUM][NUM]; int x[NUM]; int sum ; bool Same(int t) { int i; for(i=1; i<=n; i++ ) if( (a[t][i] == 1) && (x[i] == x[t]) ) return false; return true; } void BackTrack(int t ) { int i; if( t > n ) { sum ++ ; for(i=1; i<=n ;i++) printf("%d ",x[i]); printf("\n") ; } else for(i=1; i<=m; i++ ) { x[t] = i; if( Same(t) ) BackTrack(t+1); x[t] = 0; } } int main() { scanf("%d %d",&n,&m); memset(a,0,sizeof(a)); int b ,e ; while(scanf("%d%d",&b,&e) && (b||e) ) { a[b][e] = 1 ; a[e][b] = 1 ; } sum = 0; BackTrack(1); printf("Total=%d\n",sum ) ; return 0; }

n皇后问题：

在 N×N 的国际象棋棋盘上放置 N 个皇后，使得任意两个皇后不能处于同一行、同一列或同一对角线上（即彼此无法相互攻击）。‌‌

输入为n

输出为所有可能的放置情况，最后一行是方案总数，第一个数字代表第一列放置的行数，依次类推

#include <iostream> #include <cmath> using namespace std; #define NUM 20 int n; int x[NUM]; int sum; inline bool Place(int t) { int i; for (i=1; i<t; i++) if ((abs(t-i) == abs(x[i]-x[t])) || (x[i] == x[t])) return false; return true; } void Backtrack(int t) { int i; if (t>n) { sum++; for (i=1; i<=n; i++) printf(" %d", x[i]); printf("\n"); } else for (i=1; i<=n; i++) { x[t] = i; if (Place(t)) Backtrack(t+1); } } int main() { while (cin>>n) { sum = 0; Backtrack(1); printf("Total= %d\n\n", sum); } return 0; }

旅行商问题：

#include <iostream> using namespace std; #define NUM 100 int n; int m; int a[NUM][NUM]; int x[NUM]; int bestx[NUM]; int cc; int bestc; int NoEdge = -1; void Backtrack(int t) { if(t==n) { if(a[x[n-1]][x[n]]!= NoEdge && a[x[n]][1]!= NoEdge && (cc + a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc== NoEdge)) { for(int i=1; i<=n; i++) bestx[i] = x[i]; bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1]; } return; } else { for(int i=t; i<=n; i++) { if(a[x[t-1]][x[i]]!= NoEdge && (cc + a[x[t-1]][x[i]]< bestc||bestc == NoEdge)) { swap(x[t],x[i]); cc += a[x[t-1]][x[t]]; Backtrack(t+1); cc -= a[x[t-1]][x[t]]; swap(x[t],x[i]); } } } } int main() { int i, j; int from, to, length; while (scanf("%d%d", &n, &m) && n) { for (i=0; i<NUM; i++) for (j=1; j<NUM; j++) a[i][j] = NoEdge; for (i=0; i<m; i++) { scanf("%d%d%d", &from, &to, &length); a[from][to] = length; a[to][from] = length; } bestc = NoEdge; for(i=1; i<=n; i++) x[i] = i; Backtrack(2); for(j=1; j<=n; j++) printf("%d ", bestx[j]); printf("\n%d\n", bestc); } return 0; }

流水作业调度问题：

#include <iostream> using namespace std; #define NUM 20 #define infinite 10000 int n; int job[NUM][3]; int x[NUM]; int bestx[NUM]; int f1; int f2[NUM]; int f; int bestf; void Backtrack(int t) { if (t>n) { bestf = f; for (int i=1; i<=n; i++) bestx[i]=x[i]; return; } for (int i=t; i<=n; i++) { f1 += job[x[i]][1]; f2[t] = ((f2[t-1]>f1) ? f2[t-1] : f1)+job[x[i]][2]; f += f2[t]; if (f<bestf) { swap(x[t], x[i]); Backtrack(t+1); swap(x[t], x[i]); } f1 -= job[x[i]][1]; f -= f2[t]; } } int main() { int i; while (cin>>n) { memset(bestx, 0, sizeof(bestx)); memset(f2, 0, sizeof(f2)); for (i=1; i<=n; i++) scanf("%d%d", &job[i][1], &job[i][2]); bestf = infinite; f1 = 0; f = 0; for (i=0; i<=n; i++) x[i] = i; Backtrack(1); cout<<bestf<<endl; } }

子集和问题：

#include<iostream> using namespace std; #define NUM 10000 int n; int c; int cw; int bestw; int w[NUM]; int x[NUM]; int r; bool flag; void backtrack(int t) { if(t>n) { if(cw==c) { for(int i=1; i<=n; i++) if (x[i]) printf("%d ",w[i]); printf("\n"); flag = false; } return; } r -= w[t]; if (cw+w[t]<=c) { x[t] = 1; cw += w[t]; backtrack(t+1); cw -= w[t]; } if (cw+r>bestw) { x[t] = 0; backtrack(t+1); } r += w[t]; } int main() { while(scanf("%d%d",&n,&c) && (n||c)) { r = 0; for(int i=1; i<=n; i++) { scanf("%d", &w[i]); r += w[i]; } cw = 0; bestw = 0; flag = true; backtrack(1); if (flag) printf("No Solution!\n"); } return 0; }