朴素的搜索思路
1. 由于题目中要求最小的长木棍长度,则从小到大枚举len
2. 依次将小木棍填充到长度为len的长木棍内
3. 若能将小木棍用完且每一根被构造长木棍的长度为len则返回true,否则false
剪枝优化
1. 按照小木棍长度从大到小枚举(优先使用较大者可以更快充满长木棍)
2. 将所有小木棍递增编号,每一根构造的长木棍内的小木棍编号递增,防止冗余
3. 若在构造长木棍时,发现加入一根小木棍后无解,则剩下的与该小木棍相等的小木棍也跳过
4. 第一个未被使用(小木棍编号递增)的小木棍若作为新的长木棍的第一根时无解,则回溯
5. 构造长木棍时,放最后一个小木棍时无解(对照剪枝4),其实是当前能够放满,但后面的长木棍就无法再放满了,则回溯
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=70;
int n,a[N];
int len,sum;
bool st[N]; // 标记是否被搜过
/* u:当前正在构造第几根长木棍,
cur:当前构造的长木棍长度,
start:当前的长木棍内小木棍的编号
*/
bool dfs(int u,int cur,int start)
{
if(u*len==sum) return true; // 所有的长木棍构造结束,返回true
if(cur==len) return dfs(u+1,0,0); // 当前长木棍构造结束,继续构造下一个
for(int i=start;i<n;i++) // 剪枝2:编号小木棍
{
if(st[i]) continue; // 当前的小木棍已经被用过
if(cur+a[i]>len) continue; // 如没有没用过,则使用当前的小木棍
st[i] = true;
if(dfs(u,cur+a[i],i+1)) return true; // 继续枚举第i+1个小木棍
st[i] =false;
// 剪枝3:跳过所有相等的小木棍
int j=i+1;
while(j<n&&a[i]==a[j]) j++;
i = j-1; // 可以举例:假设i=3,有三个小木棍和a[i]长度相等,则经过计算后j=7
// 剪枝4:因为cur代表当前构造的长木棍长度,如果cur==0,说明一个小木棍也不能添加
if(!cur) return false;
// 剪枝5:
if(cur+a[i]==len) return false;
}
return false;
}
int main()
{
while(cin>>n,n)
{
sum=0,len=1;
for(int i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];
len = max(len,a[i]);
}
sort(a,a+n,greater<int>());// 剪枝1:从大到小排序
memset(st,0,sizeof st);
while(true)
{
if(sum%len==0&&dfs(0,0,0))
{
cout<<len<<endl;
break;
}
len++;
}
}
return 0;
}