#include <iostream>
#include <algorithm>

using namespace std;

const int maxv=64+5;

int n,len[maxv],used[maxv],dp[50*maxv+100],visited[50*maxv+100],part,sum,nowlen,ans;
bool cmp(int a,int b)
{
	return a>=b;
}

int main()
{
	while (scanf("%d",&n) && n>0)
	{
		sum=0;
		for (int i=1;i<=n;i++) scanf("%d",&len[i]);
		for (int i=1;i<=n;i++) sum+=len[i];
	
		sort(len+1,len+n+1,cmp);	
		ans=0;
		
	    for (int part=n;part>1;part--)
		if (ans==0)
		if (sum%part==0)
		{
			int ok=1,t;
			nowlen=sum/part;
			
			memset(used,0,sizeof(used));	
			
			for (int k=1;k<=part;k++)
			if (ok==1)
			{
				memset(dp,0xFF,sizeof(dp));
			
				for (int i=1;i<=n;i++)
					if (used[i]==0)
					{
						memset(visited,0,sizeof(visited));
						for (int j=nowlen-len[i];j>=0;j--)
							if (j==0 )
							{
							   if (dp[len[i]]==-1) dp[len[i]]=0;
							}
							else if (j>0)
								if (dp[j]>=0 && dp[j+len[i]]==-1)
								{
								   dp[j+len[i]]=j;
								}
					}
						
				if (dp[nowlen]>=0)
				{
					int temp=nowlen;
					while (dp[temp]>=0)
					{
						t=temp-dp[temp];		
						int p=1;
						while (len[p]!=t || used[p]==1 ) p++;
						temp=dp[temp];
						used[p]=1;
					}
				}
				else ok=0;
				
			}
	
			if (ok==1) ans=nowlen; 
		}
	    
		if (ans==0) ans=sum;
		cout<<ans<<endl;
	}
	
	return 0;
}

• Re:为什么错了，什么情况没有考虑？ (12) fisheatscats 2007-10-29 12:00:55