UVA_307

相當(dāng)于重溫了一下POJ 1011這個(gè)題目，剪枝在這個(gè)題目中顯得尤為重要。

對(duì)于這道題而言，剪枝的策略一般有下面6個(gè)：

①先將木棒長(zhǎng)度從大到小進(jìn)行排序，這樣便于后面的選擇和操作，是后面一些剪枝算法的前提。

②在枚舉原木棒長(zhǎng)度時(shí)，枚舉的范圍為max與sum/2之間，如果這個(gè)區(qū)間內(nèi)沒有找到合適的長(zhǎng)度，那么最后原木棒的長(zhǎng)度只能是sum。

③枚舉的原木棒的長(zhǎng)度只能是sum的約數(shù)。

④在深搜過程中，如果當(dāng)前木棒和前一個(gè)木棒的長(zhǎng)度是一樣的，但是前一個(gè)木棒沒有被選上，那么這個(gè)木棒也一定不會(huì)被選上。

⑤在深搜過程中，如果當(dāng)前是在拼一根新木棒的第一截，但如果把可用的最長(zhǎng)的一根木棒用上后不能拼成功的話，那么就不用再試后面的木棒了，肯定是前面拼的過程出了問題。

⑥在深搜過程中，如果當(dāng)前可用的木棒恰好能補(bǔ)上一根原木棒的最后一截，但用它補(bǔ)上之后卻不能用剩下的木棒完成后續(xù)的任務(wù)，那么也不用再試后面的木棒了，肯定是前面拼的過程出了問題。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int sum,N,n,L,a[100],vis[100];
int cmp(const void *_p,const void *_q)
{
int *p=(int *)_p;
int *q=(int *)_q;
return *q-*p;
}
int dfs(cur,complete,len)
{
int i;
if(len==L)
{
complete++;
if(complete==N)
return 1;
else
{
for(cur=0;vis[cur];cur++);
vis[cur]=1;
if(dfs(cur+1,complete,a[cur]))
return 1;
vis[cur]=0;
}
}
else
{
for(i=cur;i<n;i++)
if(!vis[i]&&a[i]<=L-len)
{
if(i!=0&&a[i]==a[i-1]&&!vis[i-1])
continue;
vis[i]=1;
if(dfs(i+1,complete,len+a[i]))
return 1;
vis[i]=0;
if(a[i]==L-len)
return 0;
}
}
return 0;
}
int main()
{
int i,j,k,max;
while(1)
{
scanf("%d",&n);
if(n==0)
break;
sum=max=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]>max)
max=a[i];
sum+=a[i];
}
qsort(a,n,sizeof(a[0]),cmp);
memset(vis,0,sizeof(vis));
for(L=max;L<=sum/2;L++)
{
if(sum%L!=0)
continue;
N=sum/L;
if(dfs(0,0,0))
break;
}
if(L>sum/2)
printf("%d\n",sum);
else
printf("%d\n",L);
}
return 0;
}

　　

轉(zhuǎn)載于:https://www.cnblogs.com/staginner/archive/2011/09/08/2171329.html

總結(jié)

以上是生活随笔為你收集整理的UVA 307 Sticks的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。