一、内容
二、思路
剪枝1： 从最大的小棒值开始拼凑，若拼凑的长度大于sum/2代表只能将所以小棒拼凑成一根。
剪枝2： 由于在题目给出的小棒可能重复，所以在搜索的过程中，若一根小棒无法拼凑，那么接下来与它长度相同的小棒都不能用上。
剪枝3： 将数组排序，从最大的小棒开始选取，这样可以减少递归次数。
剪枝4： 若拼凑成一个木条时失败，那么这个长度就一定无法拼完。比如拼长度为7的木条，始终都找不到拼凑这么长的，那么直接退出搜索。
注意vis的回溯，这样就可以避免memset重置vis。
三、代码
#include <cstdio>
#include <algorithm>
using namespace std
;
int n
, a
[105], vis
[105], sum
, ok
, len
;
bool
cmp(int a
, int b
) {
return a
> b
;
}
void dfs(int cnt
, int num
, int start
) {
if (cnt
== n
) {
ok
= 1;
return;
}
if (num
== len
) {
dfs(cnt
, 0, 1);
return;
}
for (int i
= start
; i
<= n
; i
++) {
if (vis
[i
]) continue;
if (num
+ a
[i
] <= len
) {
vis
[i
]++;
dfs(cnt
+ 1, num
+ a
[i
], i
+ 1);
vis
[i
]--;
if (ok
) return;
while (i
+ 1 <= n
&& a
[i
+ 1] == a
[i
]) i
++;
}
if (!num
|| a
[i
] + num
== len
) return;
}
}
int main() {
while (scanf("%d", &n
), n
) {
sum
= 0;
ok
= 0;
for (int i
= 1; i
<= n
; i
++) {
scanf("%d", a
+ i
);
sum
+= a
[i
];
}
sort(a
+ 1, a
+ 1 + n
, cmp
);
for (int i
= a
[1]; i
<= sum
/ 2; i
++) {
if (sum
% i
!= 0) continue;
len
= i
;
dfs(0, 0, 1);
if (ok
) {
printf("%d\n", i
);
break;
}
}
if (!ok
) {
printf("%d\n", sum
);
}
}
return 0;
}
