这是一道典型的DFS+剪枝搜索。为了描述方便，n个小木棒我们称之为小S，原始木棒我们称之为大S，n个小S的长度依次为a[1]，a[2]，…，a[n]，大S的长度为len（这个是我们要求的）。搜索的步骤如下：按len递增的顺序搜索；依次搜索每个大S由哪些小S组成，这是搜索的框架。
下面开始剪枝：
1.len>=max{a[i]} && len|sum(a[i])
2.为了避免重复搜索，令每个大S的组成中，小S的长度依次递减，这样就需要在搜索之前对a[i]排序；全部的大S的第一段小S依次递减
3.如果在某层搜索中，尝试将a[j]加入到第i个大S的组成中，如果最终a[j]没有被使用，且a[j+1]==a[j]，不需要继续尝试a[j+1]
4.如果此次是在尝试第i个大S的第一段小S a[j]，a[j]为当前可以被使用的最长的小S，如果此次尝试失败，直接退出搜索，即退回到对第i-1个大S的搜索。试想：失败说明现在使用a[j]是不可行的，那么什么时候使用a[j]呢？如果没有退出搜索，肯定会在之后的搜索中使用a[j]，因为所有的小S必须都使用。之后的a[j]和最初尝试的a[j]有什么不同呢？没有不同，它们等价，因此之后也不会成功，不需要继续搜索。
以下是我的代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
// #define LOCAL
#ifdef LOCAL
#include<time.h>
#endif
const int maxn=70;
int n,sum,max,aim,num,a[maxn];
bool used[maxn];
int cmp(const void *a,const void *b)
{
return (*(int*)b)-(*(int*)a);
}
bool dfs(int Stick,int len,int pos)
{
bool sign=(len==0?true:false);
if(Stick==num)
return true;
for(int i=pos+1;i<n;i++)
{
if(used[i]) continue;
if(len+a[i]==aim)
{
used[i]=true;
if(dfs(Stick+1,0,-1))
return true;
used[i]=false;
return false;
}
else if(len+a[i]<aim)
{
used[i]=true;
if(dfs(Stick,len+a[i],i))
return true;
used[i]=false;
if(sign) return false;
while(a[i]==a[i+1]) i++;
}
}
return false;
}
int main()
{
#ifdef LOCAL
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
while(scanf("%d",&n)==1)
{
if(n==0) break;
memset(a,0,sizeof(a));
max=sum=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
if(a[i]>max) max=a[i];
}
// Read In
qsort(a,n,sizeof(a[0]),cmp);
// Qsort
for(aim=max;aim<=sum;aim++)
if(sum%aim==0)
{
num=sum/aim;
memset(used,false,sizeof(used));
if(dfs(1,0,-1))
{
printf("%ld\n",aim);
break;
}
}
}
#ifdef LOCAL
printf("used time = %.3lf\n",(double)clock()/CLOCKS_PER_SEC);
#endif
return 0;
}
posted on 2010-01-14 22:13
lee1r 阅读(1796)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索