#define debug 0

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


#if debug
    #define NMAX 10
#else
    #define NMAX 66
#endif

#define INF 30000
int S,H,total;
int sno[NMAX];
int b[NMAX];

int tr(int stno,int heap,int last)
{
	int i;
	if(stno>=S)
		return 0;
	if(heap>=H-1)
		return 1;
	for(i=stno;i<S;i++)
	{
		if(b[i])
			continue;
		if(sno[i]>last)
			break;
		b[i]=1;
		if(sno[i]==last)
		{
			if(tr(0,heap+1,total))
				return 1;
		}
		else
		{
		
			if(tr(i+1,heap,last-sno[i]))
				return 1;
		}
		b[i]=0;
	}
	return 0;
}
int cmp(const void *a,const void *b)
{
	return *(int*)a-*(int*)b;
}

int main()
{

#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i,j,sum,max;
	scanf("%d",&S);
	while(S)
	{
		sum=0;
		max=0;
		for(i=0;i<S;i++)
		{
			scanf("%d",&sno[i]);
			sum+=sno[i];
			
		}
		qsort(sno,S,sizeof(int),cmp);
		max=sno[S-1];

		int m=sum;
		for(i=max;i<=sum;i++)
		{
			if(sum%i==0)
			{
				memset(b,0,sizeof(b));
				
				total=i;
				H=sum/i;
				if(tr(0,0,total))
				{
					printf("%d\n",total);
					break;
				}
			}
		}

		scanf("%d",&S);
	}

#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}

• Re:各位大哥，请帮手看看，已经是强剪枝了，不知为什么还超时，谢谢 (1479) 06636351401 2005-06-05 12:54:20