题目描述：
少林寺的宝贝“少林神棍”断成了n根长短不一的小木棒，现在要把这些小木棒重新拼若干跟等长的棍子，求棍长最短是多少？
思路
1，要选择简合适的搜索顺序，如果一个人物分成多步，要优先尝试可能性少的。 （优先尝试长的木棒）
2，要发现表面上的不同，实质上等效的重复状态，避免重复。
3，根据实际问题，发现剪枝方案。
重在剪枝
用程序解决：
输入：N节木棒的长度。
输出：能拼成的最小的棍子长度。
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5
代码
！1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75#include<iostream>
#include<algorithm>
#include<cstring>
#define MAX 100
using namespace std;
int vis[MAX];
int stick[MAX];
int m;
int n;
bool cmp(int &a,int &b){
return a>b;
}
//r:还没用到的木棒数目 l:仍缺少的棍子长度 返回值:能否拼成一个棍子
bool dfs(int r,int l){
if(r==0&&l==0) return true;
if(l==0) l=m;
int last,start=0;
//剪枝4：多根木棒组成一根木棍，让木棒按长度由大到小排列组成，不必搜索当前木棒比上一根木棒长的情况，因为如果此种情况可以的话
//只是相当于将组成情况不按长度大小排序，不按长度大小排序可成功那么按长度大小排序也可成功。
if(l!=m) start=last+1;
for(int i=start;i<n;i++){
if(!vis[i]&&stick[i]<=l) //尝试第i根木棍
{
//剪枝1：上次没拼成功，这次不尝试相同长度的木棒。
if(i>0){
if(vis[i-1]==0&&stick[i]==stick[i-1]) continue;
}
last=i;
vis[i]=1;
if(dfs(r-1,l-stick[i])) return true;//找到一个就return true 不继续尝试其他木棍
else {
////明本次不能用第i根木棒 ,即没拼成功，换下一根。
vis[i]=0;
////剪枝2：len[i]为第一根木棒的情况下没拼成功，则这根木棒永远不能再被用上，所以不可能全部木棒被使用，
//后续搜索全部放弃。
if(l==m||l==stick[i]) return false;
//如果正在拼的棍子用的第一根木棒拼不成 剩下的木棒也不用考虑
//剪枝3：假设len[i]为最后一根木棒，被更小木棒替换后最终能够成功，那么3必然出现在后面的某个棍子k里。
//将棍子k中的len[i]和棍子i中用来替换3的几根木棒对调，结果当然一样是成功的。这就和i原来的拼法会导致不成功矛盾。
}
}
}
return false;
}
int main(){
// freopen("11-15.txt","r",stdin);
while(1){
scanf("%d",&n);
if(n==0) break;
int totalLen=0;
for(int i=0;i<n;i++){
cin>>stick[i];
totalLen+=stick[i];
}
// 要从长到短进行尝试
sort(stick,stick+n,cmp);
for(m=stick[0];m<=totalLen/2;m++)
{
if(totalLen%m) continue;
memset( vis, 0,sizeof(vis));
if(dfs(n,m)) {
cout<<m<<endl;
break;
}
}
if(m>totalLen/2) cout<<totalLen<<endl;
}
return 0;
}