#include<iostream.h>
#include<stdlib.h>
int *stick,*isused,n;
int Connect(int leftstick,int leftlen,int len);
int compare(const void* a,const void* b);
void main()
{
	int i,j,len,sum;
	while(cin>>n)
	{
		if(n == 0) break;
		sum = 0;
		stick = new int[n] ; isused = new int[n];
		for(i = 0 ; i < n ; i++)
		{
			cin>>stick[i]; sum += stick[i]; isused[i] = 0;
		}
		qsort(stick,n,sizeof(int),compare);
		for(len = stick[0] ; len <= sum ; len++)
		{
			if(sum % len == 0)
			{
				if(Connect(sum,len,len)) { cout<<len<<endl; break;}		
				for(j = 0 ; j < n ; j++) isused[j] = 0 ;
			}
		}
		delete []stick; delete []isused;
	}
}
int compare(const void* a,const void* b)
{
	return *(int*)b - *(int*)a ;
}
int Connect(int leftstick,int leftlen,int len)
{
	if(leftstick == 0 && leftlen == 0) return 1;
	if(leftlen == 0) leftlen = len;
	int j;
	for(j = 0 ; j < n ; j++)
	{
		if(isused[j] == 0 && stick[j] <= leftlen)
		{
			isused[j] = 1; 
			if(Connect(leftstick-stick[j],leftlen-stick[j],len)) return 1;
			isused[j] = 0 ;	
		}
	}
	return 0;
}

• Re:大侠 帮帮忙 怎么会超时？ 已经郁闷了一上午了 (1186) dage181818 2006-06-12 00:40:06