非常经典的搜索剪枝，剪枝说明见程序：
|
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 |
#include <cstdio>#include <algorithm>using
namespace std;int l,total,n,sum;struct
node{ int
l; bool
flag; friend
bool operator < (const
node &a,const
node &b) { return
a.l>b.l; }}stick[100];bool
dfs(int
s,int nl,int
pos){ if(s==total-1)return
true; //最后一根不必搜，因为加起来一定为l for(int
i=pos+1;i<=n;i++) //记录上一次搜到的地方，不要从第一个重新开始搜 { if(stick[i].flag)continue; if(nl+stick[i].l==l) { stick[i].flag=true; if(dfs(s+1,0,0))return
true; //下一根则需要重新搜索 stick[i].flag=false; return
false; } else
if(stick[i].l+nl<l) { stick[i].flag=true; if(dfs(s,nl+stick[i].l,i))return
true; stick[i].flag=false; if(nl==0)return
false; //如果第一根都无法用上，一定是失败的 while(stick[i].l==stick[i+1].l)i++; //避免重复搜索同一根 } } return
false;}int
main(){ while(scanf("%d",&n),n!=0) { sum=0; for(int
i=1;i<=n;i++) { scanf("%d",&stick[i].l); sum+=stick[i].l; stick[i].flag=false; } sort(stick+1,stick+n+1);//排序加速 for(l=stick[1].l;l<=sum;l++) //从最长的作为循环的开始，而不是1，因为不可能比其小 if(sum%l==0){ //注意可以组成sum的最小长度一定是sum的约数 total=sum/l; if(dfs(0,0,0)) { printf("%d\n",l); break; } } } return
0;} |
原文：http://www.cnblogs.com/forever97/p/3542992.html