问题:
http://poj.org/problem?id=3400思路:
这题就是个悲剧...
应该算是简单的深搜题，结果花了我一个上午
画了好几颗递归调用树也不知道为什么会出错...抓狂...
最后发现，一直出错的原因是在写代码的时候将递归函数的参数直接修改，导致后续的“同一层”的回溯调用出错，啊啊啊...
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 11
5 struct Stone {
6 int weight;
7 int cost;
8 }stones[MAX_LEN];
9 int N, D;
10 int total_cost, max_cost, hash[MAX_LEN];
11
12 void
13 dfs(char bunker, int weight_a, int cost_a, int weight_b, int cost_b)
14 {
15 int i, w, c, mark = 0;
16 if(total_cost-cost_a<=max_cost)
17 return;
18 for(i=0; i<N; i++) {
19 if(!hash[i]) {
20 mark = 1;
21 hash[i] = 1;
22 switch(bunker) {
23 case 'A':
24 w = weight_a+stones[i].weight;
25 c = cost_a+stones[i].cost;
26 if(w-weight_b <= D)
27 dfs('A', w, c, weight_b, cost_b);
28 else
29 dfs('B', w, c, weight_b, cost_b);
30 break;
31 case 'B':
32 w = weight_b+stones[i].weight;
33 c = cost_b+stones[i].cost;
34 if(w-weight_a <= D)
35 dfs('B', weight_a, cost_a, w, c);
36 else
37 dfs('A', weight_a, cost_a, w, c);
38 break;
39 }
40 hash[i] = 0;
41 }
42 }
43 if(!mark)
44 max_cost = max_cost<cost_b ? cost_b : max_cost;
45 }
46
47 int
48 main(int argc, char **argv)
49 {
50 int i;
51 while(scanf("%d %d", &N, &D) != EOF) {
52 total_cost = 0;
53 for(i=0; i<N; i++) {
54 scanf("%d %d", &stones[i].weight, &stones[i].cost);
55 total_cost += stones[i].cost;
56 }
57 max_cost = 0;
58 memset(hash, 0, sizeof(hash));
59 dfs('A', 0, 0, 0, 0);
60 printf("%d\n", max_cost);
61 }
62 }