剪枝是王道!!!
if (sum+number[j]<=Max)
就这么一个简单的剪枝,时间从10+秒变成了0.85
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4
5 int number[31];
6
7 bool used[31];
8
9 int get[31];
10
11 int Max;
12
13 bool foundone = false;
14
15 bool compare(int a, int b)
16 {
17 return a < b;
18 }
19
20 bool binarysearch(int beg, int end,int value)
21 {
22 bool found = false;
23 int mid = 0;
24
25 while ( beg <= end )
26 {
27 mid = ( beg + end ) / 2 ;
28 if ( number[mid] > value )
29 end = mid-1 ;
30 else if ( number[mid] < value )
31 beg = mid+1 ;
32 else
33 {
34 found = true;
35 break;
36 }
37 }
38 return found;
39 }
40 void solve(int total,int start,int deep,int target,long sum)
41 {
42 if (deep==target)
43 {
44 if (binarysearch(0,total-1,sum)==true)
45 {
46 foundone = true;
47 for (int i = 0; i < target; i++)
48 {
49 if (i!=target-1)
50 printf("%d+",get[i]);
51 else
52 printf("%d=",get[i]);
53 }
54 printf("%d\n",sum);
55 }
56 }
57 else
58 for (int j = start; j < total; j++)
59 if (used[j]==false)
60 {
61 if (sum+number[j]<=Max)
62 {
63 sum+=number[j];
64 used[j] = true;
65 get[deep] = number[j];
66 solve(total,j+1,deep+1,target,sum);
67 get[deep] = 0;
68 sum-=number[j];
69 used[j] = false;
70 }
71 }
72 }
73 int main()
74 {
75 int N;
76 cin >> N;
77 for (int i = 0; i < N; i++)
78 {
79 int M;
80 cin >> M;
81 foundone = false;
82
83 for (int j = 0; j < M; j++)
84 scanf("%d",&number[j]);
85
86 sort(number,number+M,compare);
87
88 for (int j = 0; j < M; j++)
89 used[j] = false;
90
91 Max = number[M-1];
92
93 for (int j = 2; j < M; j++)
94 solve(M,0,0,j,0);
95
96 if (!foundone)
97 cout << "Can't find any equations." << endl;
98
99 cout << endl;
100 }
101 //system("pause");
102 return 0;
103 }