#include<iostream>
#include<stdlib.h>
#include<memory.h>
using namespace std;
int n;
int stick[65];
int len;
int sumlen=0;
bool used[65];
int nLastStickNo=0;
bool DFS(int UnusedStick ,int left )
{
if(UnusedStick==0&&left==0)
	return true;
if(left==0)
	left=len;
int nStartNo = 0;
	if( left != len) //剪枝
		nStartNo = nLastStickNo + 1;

for(int i = nStartNo;i < n;i ++)
{
	if(!used[i]&&stick[i]<=left)
	{
		if(i>0)
		{
			if(used[i-1]==0&&stick[i]==stick[i-1])
				continue;
		}
		used[i]=true;
		nLastStickNo = i;
		if(DFS(UnusedStick-1,left-stick[i]))
			return true;
		else
			{
			used[i]=false;
			if(stick[i]==left||left==len)//剪枝
				return false;
			}
}
}
return false;
}

int compare(const void*x,const void *y)
{
return *(int*)y- *(int*)x;
}

int main()
{
	while(true)
	{
	cin>>n;
	if(n==0)
	break;
	int i,j;
	for(i=0;i<n;i++)
	{
		cin>>stick[i];
		sumlen+=stick[i];
	}
	qsort(stick,n,sizeof(int),compare);

	if(stick[0]>(sumlen/2))
		cout<<sumlen<<endl;//一个优化

	for(len=stick[0];len<=sumlen/2;len++)
	{
		if(sumlen%len)
			continue;
		memset( used, 0,sizeof(used));
		if(DFS(n,len))
			{
			cout<<len<<endl;
			break;
			}

	}
memset(stick,0,sizeof(stick));
sumlen=0;
memset( used, 0,sizeof(used));
len=0;
	}
	return 0;
}

• Re:那位大牛谁能找出错啊……………………万谢！！ (1510) pkusirius 2010-02-06 23:58:05