题意:
有若干根小木棍是由 若干根相等的大木棍随意砍断而得
求初始木棍的最小长度
优化(剪枝)方式
优化1:
从大到小排序,先枚举大的,后面的空间也就小了,可以减少后面的分支; 而且最终的长度一定是所有小木棍总和的因数
优化2 见代码内部
#include <bits/stdc++.h>
using namespace std;
const int N = 70;
int n;
int w[N];
bool st[N];
int len, sum;
bool cmp(int a, int b)
{
return a > b;
}
bool dfs(int u, int cur, int start) //第u根木棍, 第u根木棍的当前长度,当前下标
{
if(u * len == sum) return true;
if(cur == len) return dfs(u + 1, 0, 0);
for(int i = start; i < n; i ++)
{
if(st[i]) continue;
if(cur + w[i] <= len)
{
st[i] = true;
if(dfs(u, w[i] + cur, i + 1)) return true;
st[i] = false; //回溯
}
//剪枝
/* !cur: 如果第一根小木棍一直都没找到配对的,那么一定就是失败的
w[i] + cur == len :
第u层的最后一根木棍拼好之后,就会拼下一层的木棍;当下面的层数都可以拼好之后,
就会返回给上一层,直到返回到最后的主函数里面.
一旦有一层的结果是false,就会返回到上一层的最后一根小木棍, 而此时,
这根木棍满足 cur + w[i] = len, 而前面的dfs(u, w[i] + cur, i + 1)都不成立,
所以说这最后一根木棍无论如何都找不到解, 因为他在这根木棍中会使得无解
那么即便是去了别的木棍还是无解*/
if(!cur || w[i] + cur == len) return false;
// 如果说第i根小木棍失败了,那么和这根一样的木棍也会失败
int j = i + 1;
while(j < n && w[i] == w[j]) j ++;
i = j - 1;
}
return false;
}
int main()
{
while(cin >> n, n)
{
len = 0; // 列举的原木棍长度
sum = 0; // 总长度, 最终一定会满足 sum % len == 0
for(int i = 0; i < n; i ++)
{
cin >> w[i];
len = max(w[i], len); // len一定大于所有的子木棍
sum += w[i];
}
sort(w, w + n, cmp);
memset(st, 0, sizeof st);
while(true)
{
if(sum % len == 0 && dfs(0, 0, 0))
{
cout << len << endl;
break;
}
len ++;
}
}
return 0;
}