回溯例题（计算机算法设计与分析）

P153：子集和问题

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int n,s;
 6 bool vis[100];
 7 int a[100];
 8 bool calc(int cur) {
 9     if(cur==s) {
10         for(int i=0;i<n;i++) {
11             if(vis[i])
12                 printf("%d ",a[i]);
13         }
14         puts("");
15         return true;
16     }
17     else {
18         for(int i=0;i<n;i++) {
19             if(!vis[i]) {
20                 vis[i] = true;
21                 if(calc(cur+a[i]))
22                     return true;
23                 vis[i] = false;
24             }
25         }
26     }
27     return false;
28 }
29 
30 int main()
31 {
32     freopen("in.txt","r",stdin);
33     scanf("%d%d",&n,&s);
34     for(int i=0;i<n;i++) {
35         scanf("%d",&a[i]);
36     }
37     if(!calc(0))
38         puts("No Solution!");
39     return 0;
40 }

View Code

P152：最小重量机器设计问题

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int n,m,c;
 6 const int maxn = 100;
 7 
 8 struct Node {
 9     int w;
10     int c;
11     int id;
12     bool operator < (const Node & rhs) const {
13         if(w!=rhs.w)
14             return w < rhs.w;
15         else return c < rhs.c;
16     }
17 };
18 
19 vector<Node> nn[maxn];
20 
21 int ccc[maxn][maxn];
22 int www[maxn][maxn];
23 bool vis[maxn][maxn];
24 
25 bool calc(int cur,int cc) {
26     if(cur>=n&&cc<=c) {
27         printf("%d
",cc);
28         for(int i=0;i<n;i++) {
29             for(int j=0;j<m;j++) {
30                 if(vis[i][j]) {
31                     printf("%d ",nn[i][j].id);
32                     break;
33                 }
34             }
35         }
36         puts("");
37         return true;
38     }
39 
40     else {
41         for(int i=0;i<m;i++) {
42             vis[cur][i] = true;
43             int cx = cc+nn[cur][i].c;
44             if(calc(cur+1,cx))
45                 return true;
46             vis[cur][i] = false;
47         }
48     }
49     return false;
50 }
51 
52 
53 int main()
54 {
55     freopen("in.txt","r",stdin);
56     scanf("%d%d%d",&n,&m,&c);
57     for(int i=0;i<n;i++) {
58         for(int j=0;j<m;j++) {
59             scanf("%d",&ccc[i][j]);
60         }
61     }
62 
63     for(int i=0;i<n;i++) {
64         for(int j=0;j<m;j++) {
65             scanf("%d",&www[i][j]);
66         }
67     }
68 
69     for(int i=0;i<n;i++) {
70         for(int j=0;j<m;j++) {
71             nn[i].push_back((Node){www[i][j],ccc[i][j],j+1});
72         }
73         sort(nn[i].begin(),nn[i].end());
74     }
75 
76     calc(0,0);
77 
78     return 0;
79 }

View Code

P152：运动员最佳配对问题

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 100;
 6 
 7 int n;
 8 int p[maxn][maxn];
 9 int q[maxn][maxn];
10 bool vis[maxn];
11 
12 int ans;
13 void calc(int cur,int cc) {
14     if(cur>n) {
15         ans = max(ans,cc);
16     }
17     for(int i=0;i<n;i++) {
18         if(!vis[i]) {
19             vis[i] = true;
20             calc(cur+1,cc+p[cur][i]*q[i][cur]);
21             vis[i] = false;
22         }
23     }
24 }
25 
26 int main()
27 {
28     freopen("in.txt","r",stdin);
29     scanf("%d",&n);
30     for(int i=0;i<n;i++) {
31         for(int j=0;j<n;j++) {
32             scanf("%d",&p[i][j]);
33         }
34     }
35     
36     for(int i=0;i<n;i++) {
37         for(int j=0;j<n;j++) {
38             scanf("%d",&q[i][j]);
39         }
40     }
41     
42     calc(0,0);
43     printf("%d
",ans);
44     
45     return 0;
46 }

View Code

P196：n皇后问题

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 25;
 6 int C[maxn];
 7 int n;
 8 void calc(int cur) {
 9     if(cur>=n) {
10         for(int i=0;i<n;i++)
11             printf("%d ",C[i]+1);
12         puts("");
13         return;
14     }
15     else {
16         for(int i=0;i<n;i++) {
17             int ok = 1;
18             C[cur] = i;
19             for(int j=0;j<cur;j++) {
20                 if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j]) {
21                     ok = 0;
22                     break;
23                 }
24             }
25             if(ok) {
26                 calc(cur+1);
27                 return;
28             }
29         }
30     }
31     return;
32 }
33 
34 int main()
35 {
36     scanf("%d",&n);
37     calc(0);
38     return 0;
39 }

View Code