做了这题，才知道剪枝的厉害。。。
正要的剪枝：
如果当前木棍能恰好填满一根原始木棍，但因剩余的木棍无法组合出合法解而返回，那么让我们考虑接下来的两种策略，一是用更长的木棍来代替当前木棍，显然这样总长度会超过原始木棍的长度，违法。二是用更短的木棍组合来代替这根木棍，他们的总长恰好是当前木棍的长度，但是由于这些替代木棍在后面的搜索中无法得到合法解，当前木棍也不可能替代这些木棍组合出合法解。因为当前木棍的做的事这些替代木棍也能做到。所以，当出现加上某根木棍恰好能填满一根原始木棍，但由在后面的搜索中失败了，就不必考虑其他木棍了，直接退出当前的枚举
考虑每根原始木棍的第一根木棍，如果当前枚举的木棍长度无法得出合法解，就不必考虑下一根木棍了，当前木棍一定是作为某根原始木棍的第一根木棍的，现在不行，以后也不可能得出合法解。也就是说每根原始木棍的第一根小木棍一定要成功，否则就返回。（剪枝四）
1 #include<stdio.h> 2 3 #include<string.h> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define max 70 8 9 bool vis[max]; 10 int a[max],n; 11 12 bool cmp(int x,int y){ 13 return x>y; 14 } 15 16 bool dfs(int len,int cur,int cnt){ 17 if(cur==len&&cnt==n){ 18 return true; 19 } 20 if(len==cur){ 21 cur=0; 22 } 23 for(int i=0;i<n;i++){ 24 if(vis[i]){ 25 continue; 26 } 27 if(cur+a[i]<=len){ 28 vis[i]=true; 29 if(dfs(len,cur+a[i],cnt+1)){ 30 return true; 31 } 32 vis[i]=false; 33 } 34 if(a[i]==len-cur||len-cur==len){ 35 break; 36 } 37 for(int j=i+1;j<n;j++){ 38 if(a[j]!=a[i]){ 39 i=j-1; 40 break; 41 } 42 } 43 } 44 return false; 45 } 46 47 int main(){ 48 while(scanf("%d",&n),n){ 49 int sum=0; 50 for(int i=0;i<n;i++){ 51 scanf("%d",&a[i]); 52 sum+=a[i]; 53 } 54 memset(vis,false,sizeof(vis)); 55 sort(a,a+n,cmp); 56 int ans; 57 for(int i=a[0];i<=sum;i++){ 58 if(sum%i){ 59 continue; 60 } 61 if(dfs(i,0,0)){ 62 ans=i; 63 break; 64 } 65 } 66 printf("%d ",ans); 67 } 68 }