剪枝是王道!!!

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 }