POJ 1011 Sticks

非常经典的搜索题，很多剪枝技巧在里面!!
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <string.h>
 7 
 8 using namespace std;
 9 
10 int cmp(const void *a ,const void *b)
11 {
12     return *(int*)b-*(int*)a;
13 }
14 
15 int a[70];
16 int n;
17 int vis[70];
18 int sum;
19 
20 int ko(int unused,int left, int target)
21 {
22       if(unused==0&&left==0)
23       {
24           return 1;
25       }
26       if(left==0)
27       {
28           left=target;
29       }
30 
31       for(int i=0;i<n;i++)
32       {
33           if(vis[i]==1) continue;
34           if(a[i]>left) continue;
35 
36           vis[i]=1;
37           if(ko(unused-1,left-a[i],target))
38             return 1;
39           vis[i]=0;
40 
41           if(a[i]==left||left==target)
42             return 0;
43 /*
44 如果当前木棍能恰好填满一根原始木棍，但因剩余的木棍无法组合出合法解而返回，那么让我们考虑接下来的两种策略，一是用更长的木棍来代替当前木棍，显然这样总长度会超过原始木棍的长度，违法。二是用更短的木棍组合来代替这根木棍，他们的总长恰好是当前木棍的长度，但是由于这些替代木棍在后面的搜索中无法得到合法解，当前木棍也不可能替代这些木棍组合出合法解。因为当前木棍的做的事这些替代木棍也能做到。所以，当出现加上某根木棍恰好能填满一根原始木棍，但由在后面的搜索中失败了，就不必考虑其他木棍了，直接退出当前的枚举。
45 
46 */
47  
48       }
49 
50       return 0;
51 
52 }
53 
54 
55 int main()
56 {
57     while(cin>>n&&n)
58     {
59         sum=0;
60         memset(a,0,sizeof(a));
61         for(int i=0;i<n;i++)
62         {
63             cin>>a[i];
64             sum+=a[i];
65         }
66 
67 
68         qsort(a,n,sizeof(a[0]),cmp);
69         memset(vis,0,sizeof(vis));
70 
71         for(int i=n;i>0;i--)
72         {
73             if(sum%i!=0)  continue;
74             if(sum/(double)i<=(double)a[i]) continue;
75             if(ko(n,0,sum/i))
76             {
77                 cout<<sum/i<<endl;
78                 break;
79             }
80         }
81     }
82 
83     return  0;
84 }