注意所有木棒都是等长的
思路:把所有木棒按长度从大到小排列,选第一个木棒得长度作为最短可能长度,用所有木棒全都拼成第一根木棒的长度,拼不出来就将该长度+1,继续拼。反正木棒最长也就50,暴搜是可行的。
附Y总的剪枝三法
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 70;
int n;
int sticks[N];
bool st[N];
int sum, length;
bool dfs(int u, int cur, int start) //u:拼第u根木棒,cur:正在拼的木棒长度
{ //start:开始搜索的下标
if (u * length == sum) return true;
if (cur == length) return dfs(u + 1, 0, 0); //当前长度拼到length了,开始拼下一根
for (int i = start; i < n; i ++ )
{
if (st[i]) continue; //当前木棒用过了,抬走,下一个
int l = sticks[i]; //l为第i根木棍长度
if (cur + l <= length) //正在拼的木棒长度+当前木棒长度<=目标木棒长度
{
st[i] = true;
if (dfs(u, cur + l, i + 1)) return true;
st[i] = false; //恢复现场
}
//走到这一步说明当前拼接已失败,开启失败三重剪枝
if (!cur || cur + l == length) return false; //剪枝3-2和剪枝3-3
int j = i + 1; //剪枝3-1跳过长度相同的木棒
while (j < n && sticks[j] == l) j ++ ;
i = j - 1;
}
return false;
}
int main()
{
while (cin >> n, n)
{
sum = length = 0;
for (int i = 0; i < n; i ++ )
{
int l;
cin >> l;
sticks[i] = l;
sum += l;
length = max(length, l); //储存输入木棒的最大长度
}
sort(sticks, sticks + n, greater<int>()); //剪枝1:木棒长度从大到小排序
memset(st, 0, sizeof st);
while (true)
{ //搜第0根木棒,当前长度是0,从下标0开始搜
if (sum % length == 0 && dfs(0, 0, 0)) //剪枝2:按木棒长度从小到大枚举
{ //且只有sum % len == 0 时,长度才是有效的
cout << length << endl;
break;
}
length ++ ;
}
}
return 0;
}