#include <iostream.h>
#include <fstream.h>
int total,stick[200],n,flag;
int used[200];
int len;
int sift(int a[],int i,int n1)
{
	int j,t;
	j=2*i;
	t=a[i];
	while(j<=n1){
		if (j<n1 && a[j]<a[j+1])
			j++;
		if (t<a[j]){
			a[i]=a[j];
			i=j;
			j=2*i;
		}
		else break;
	}
	a[i]=t;
	return 0;
}
	
int heap_sort(int a[],int n)
{
	int i,t;
	for(i=n/2;i>=1;i--)
		sift(a,i,n);
	for(i=n;i>=2;i--){
		t=a[1];
		a[1]=a[i];
		a[i]=t;
		sift(a,1,i-1);
	}
	return 0;
}
		
	
int search(int p,int now)
{
	int i;
	if (flag) return 0;
	if (p==total && now==len){ 
		flag=1;
		return 0;
	}
	if (now==len){
	       	p++;
		now=0;
	}
	for(i=1;i<=n;i++){
		if (used[i]==0 && (now+stick[i])<=len) {
			used[i]=1;
			if (!flag) search(p,now+stick[i]);
			used[i]=0;
		}
	}
	return 0;
}
int main()
{
	int i;
	int max,sum;
	ifstream cin("input.dat");
	while(cin>>n && n!=0){
		sum=0;
		max=0;
		flag=0;
		memset(used,0,sizeof(used));
		for(i=1;i<=n;i++){
			cin>>stick[i];
			if (stick[i]>max) max=stick[i];
			sum+=stick[i];
		}
		heap_sort(stick,n);
		for(len=max;len<=sum;len++){
			if (sum%len==0){
			       	total=sum/len;
				search(1,0);
			}
			if (flag) break;
		}
		cout<<len<<endl;
	}
	return 0;
}
	

• Re:这个题怎么剪枝呀 怎样去掉那些重复的状态 (620) xiaomi 2004-03-26 01:11:11
  • Re:这个题怎么剪枝呀 怎样去掉那些重复的状态 (47) xiaomi 2004-03-26 01:12:52
    • Re:这个题怎么剪枝呀 怎样去掉那些重复的状态 (87) wanglei 2004-03-26 11:12:29
      • 这样剪不对呀 (44) wanglei 2004-03-26 11:13:13
        • Re:这样剪不对呀 (1284) xiaomi 2004-03-26 15:30:34