#include "stdio.h"
#include "stdlib.h"
int lenth[65]={0};
int visit[65]={0};
int stick;
int cmp(const void *r1,const void *r2)
{
	return *(int *)r2-*(int *)r1;
}
bool search(int loc,int remain){//loc 是当前搜索的地址下标，remain是剩余和

	if(loc>=stick)
		return false;//if 访问到最后也没有 发现解 

	if(visit[loc]==0)//这个 棍子没有访问过
	{
		if(lenth[loc]==remain)//正好的情况
		{
			visit[loc]=1;
			return true;
		}
		if(lenth[loc]<remain){//本棍子的长度 小于Remain
			
		    if(search(loc+1,remain-lenth[loc]))//搜素1 ：要这个棍子
		    {	
				visit[loc]=1;	
				return true;
		    }
		
		    if(search(loc+1,remain))//2 不要这个棍子
				return true;
		    return false;//如果要和不要都不可以就说明这个解不行了
		}
		if(lenth[loc]>remain)//这个棍子 大于余量 不要这个棍子
			return search(loc+1,remain);
	}
	else//棍子已经取了 
		return search(loc+1,remain);
}
bool test(int max)
{
	int m;

	for(m=0;m<stick;m++)//从棍子0 到stick-1找

	{
		if(visit[m]==0)/没有访问就找
		{
			if(lenth[m]==max)//Max是当前我测试的 单棍长度 如果这个长度直接相等了，就直接选了这个棍子
			{
				visit[m]=1;
				continue;
			}
			else//否则 找棍子
			{
				if(search(m,max)){
				
					visit[m]=1;
					
				}
				else//没有找到BREAK
					break;
			}

		}
		else
			continue;

		
	}
	if(m==stick)//找到头了说明 全有解 则true
		return true;
	else
		return false;
}
int main(){

	int max;
	while(scanf("%d",&stick)){
		int i=0;
		max=0;
		while(i<65)
		{
			lenth[i]=0;
			visit[i]=0;
			i++;
		}
	    int sum=0;
		if(stick==0)
			break;
		int k;
            //算出棍子和  因为整数个 如果单长不能被sum整除 不可能是棍子长 并且单个长一定大于等于 分割棍子的最大那个  以裁剪
		for(k=0;k<stick;k++)
		{
			scanf("%d",lenth+k);
			if(*(lenth+k)>max)
				max=*(lenth+k);
			sum+=*(lenth+k);
		}
                 //一个棍子，直接搞掉
		if(stick==1)
		{

			printf("%d\n",sum);
			continue;
		}
		//棍子排序，从大到小
		qsort(lenth,stick,sizeof(int),cmp);
                找棍子长度
		for(k=max;k<=sum;k++)
		{
		  
			if(sum%k==0)
			{
			    for(i=0;i<65;i++)
				  visit[i]=0;
                if(test(k))
				{
					printf("%d\n",k);
					break;
				}

			}
		}		
		
	}
	return 0;
}

• Re:所有数据都顺出 为什么WA？那位大牛帮看看吧---万分感谢啦 注释很详实 (17) hopeztm 2009-05-30 22:25:37