#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
int num,sum,max;//max纪录拼出的最小木棒的长度
int lenth[70],use[70]={0};//lenth纪录长度，use纪录是否被使用
int myComp(const void *a,const void *b)
{
	int *c=(int *)a;
	int *d=(int *)b;
	return *d-*c;
}
int choose(int max1,int num1)
{
	int a,b,c,d;
	if(num1==0&&max1==0) return 1;//如果木棒没有剩余且都拼成max长度，，即剩余的max1长度为0，，成功
	if(num1==0) return 0;//如果木棒没有剩余，，但max1不为0 ，失败
	if(max1==0) max1=max;//拼完一根后拼下一根 
	for(a=0;a<num;a++)
	{
		if(lenth[a]<=max1&&use[a]==0)//找到没有使用过的木棒
		{
			max1-=lenth[a];//使用木棒
			use[a]=1;
			num1--;
			if(choose(max1,num1)) return 1;//如果剩余的木棒能拼好，，则成功，，，否则恢复当前拼得木棒，，找下一根
			max1+=lenth[a];
			use[a]=0;
			num1++;
		}
	}
	return 0;
}
int main()
{
	int a;
	for(;;)
	{
		sum=0;
		memset(use,0,sizeof(use));
		scanf("%d",&num);
		if(num==0) break;
		for(a=0;a<num;a++)
		{
			scanf("%d",&lenth[a]);
			sum+=lenth[a];//用sum来记录长度和
		}
		qsort(lenth,num,sizeof(lenth[0]),myComp);//将木棒从长到短排序 
		for(max=lenth[0];;max++)
		{
			if(sum%max!=0) continue;
			if(choose(max,num)) break;
		}
		printf("%d\n",max);
	}
}
		

• Re:我得程序怎么加入排除同一长度木棒的算法？？？（附代码有注释） (5) 00630015 2007-07-21 20:34:29