問題:
http://poj.org/problem?id=3400思路:
這題就是個(gè)悲劇...
應(yīng)該算是簡單的深搜題，結(jié)果花了我一個(gè)上午
畫了好幾顆遞歸調(diào)用樹也不知道為什么會(huì)出錯(cuò)...抓狂...
最后發(fā)現(xiàn)，一直出錯(cuò)的原因是在寫代碼的時(shí)候?qū)⑦f歸函數(shù)的參數(shù)直接修改，導(dǎo)致后續(xù)的“同一層”的回溯調(diào)用出錯(cuò)，啊啊啊...
代碼:
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 }