> #include <stdio.h>
> #include <string.h>
> 
> int n,L[101],sum,max,Len,N;
> 
> bool got[5001],used[101];
> int pre[5001];
> 
> /*
> void Q_sort(int p,int r){
> 	if(p >= r) return ;
> 	int i = p - 1, j = r + 1, x = L[(p + r) / 2],t;
> 	while(true){
> 		do j-- while(L[j] > x);
> 		do i++ while(L[i] < x);
> 		if(i  >= j) break;
> 		t = L[i]; L[i] = L[j]; L[j] = t;
> 	}
> 	Q_sort(p,j);
> 	Q_sort(j+1,r);
> }
> 
> */
> 
> bool test(){
> 	memset(used,0,sizeof(used));
> 
> 	int i,j,k;
> 	for(i=0; i<N; i++){		
> 		memset(got,0,sizeof(got)); got[0] = true;
> 		memset(pre,0,sizeof(got));
> 		for(j=0; j<n; j++)
> 			if (! used[j] ){
> 				for(k = L[j]; k <= Len; k++)
> 					if(got[k - L[j]]){
> 						pre[k] = j; got[k] = true; 
> 					}
> 				if(got[Len]) break;
> 			}	
> 		if(! got[Len] ) return 0;
> 		k = Len;
> 		while (k > 0){
> 			used[pre[k]] = true;
> 			k -= L[pre[k]];
> 		}
> 	}
> 
> 
> 	return true;
> }
> 
> int main(){
> 	int i;
> 
> 	while(scanf("%d",&n), n != 0){
> 		for(i = max = sum = 0; i<n; i++){
> 			scanf("%d",&L[i]); sum += L[i];
> 			if(L[i] > max) max = L[i];
> 		}
> 
> 	//	Q_sort(0,n-1);
> 		for(N = n; N>0; N--)
> 			if(sum % N == 0){
> 				Len = sum / N; if(Len < max) continue;
> 				if(test()){
> 					printf("%d\n",Len); break;
> 				}
> 			}	
> 	}
> 	
> 	return 0;
> }

• 请问。。 (59) lemongxr 2003-11-24 21:14:47