题意：给你很多短的棒子，它们的长度告诉你，它们是由很多根长的棒子截出来的，问你这些短的棒子可以组成很多个相等的长棒子，求单个长棒子最短是多少？
想法：设所有棒子的总长为sum，seglen为单个长棒子的长度。通过题意，你需要知道当前seglen还有多少？sum还有多少可以用。
剪枝：1.seglen必定不小于所有短木棒里面最长的那个。
2.seglen的长度肯定能被sum整除。
3.长度数组从大到小排序。
4.如果剩下的剪枝~在程序里……
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,slen[70];
int sum,seg_len;
int vis[70];
bool cmp(int x,int y)
{return x>y;
}
void Input()
{sum=0;for(int i=1;i<=n;i++){scanf("%d",&slen[i]);sum+=slen[i];}
}
int dfs(int pos,int seglen,int restlen)
{if(restlen==seglen) return 1;//余下的总长度等于余下的一段的长度 if(restlen==seg_len) return 1;//余下的总的长度等于要求的一段总长度 for(int i=pos;i<=n;i++){if(vis[i]||slen[i]>seglen) continue;vis[i]=1;if(seglen==slen[i])//KEY1{if(dfs(1,seg_len,restlen-slen[i])) return 1;}else if(dfs(i+1,seglen-slen[i],restlen-slen[i])) return 1;vis[i]=0;if(seglen==slen[i]) return 0;//对KEY1第一个if的判定 if(restlen==sum) return 0;//对第一次的进行剪枝if(seglen==seg_len) return 0;//对KEY1第二个if的判定 while(slen[i]==slen[i+1]) i++;//一样的没有必要再取了 }return 0;
}
void treatment()
{sort(slen+1,slen+1+n,cmp);memset(vis,0,sizeof(vis));for(int i=n;i>=1;i--){if(sum%i==0&&sum/i>=slen[1]){seg_len=sum/i;if(dfs(1,seg_len,sum)) break;}}printf("%d\n",seg_len);
}
int main()
{while(~scanf("%d",&n),n){Input();treatment();} return 0;
}