這是一道典型的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 閱讀(1805)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索