#include <stdio.h>
#include <string.h>
#include <stdlib.h> 
int stick[100];
int used[100];
int n, //木棍数量 
	Max,//木棍最大长度 
	num,//相等长度木棍的数量  
	F,//全局变量表示是否有结果 
	res;//最后结果； 
int cmp(const void *a,const void *b)
{
	return *(int *)b-*(int *)a;
}
void Dosearch(int index,int cur_length,int length,int cur_num)
{
	if(F)return;
	if(cur_length==length){
		cur_num++;
    	if(cur_num==num-1){
    		printf("%d\n",length);
    		F = 1;
    		return;
    	}
		Dosearch(0,0,length,cur_num);
	}		
   	for(int i=index;i<n;i++)
   	{
   		if(!used[i]&&cur_length+stick[i]<=length)
   		{		
   			used[i]=1;
   			Dosearch(i+1,cur_length+stick[i],length,cur_num);
   			if(F)return;
   			used[i]=0;   
   			if(stick[i]==length-cur_length)return;
   		}
   	}
}
void doneSearch(int sum){
	F=0;
	for(int i=Max;i<=sum;i++)
	{
		if(sum%i!=0&&!F)
			continue;
		memset(used,0,sizeof(used));
		num=sum/i;
		used[0]=1;
		Dosearch(0,stick[0],i,0);
		if(F){
			return;
		}
	}
}
int main()
{

	while(scanf("%d",&n)&&n)
	{
		int sum=0;
		Max=0;
		for(int i=0;i<n;i++){
			scanf("%d",&stick[i]);
			sum+=stick[i];			
			if(stick[i]>Max)
				Max=stick[i];		
		}
		qsort(stick,n,sizeof(int),cmp);
		doneSearch(sum);
	}
	return 0;
}

这个还应该怎么优化呢？？

• (1)剩下的最长的木棍一定要在下一次合并掉(2)同样长度的如果已经试过一次不行就可以不再尝试 (0) zentropy 2007-09-04 00:02:58
  • 赞这两句话 (0) bkdream 2007-10-17 21:13:56