#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <functional>
#define REP(i,n)	for(i=0;i<n;i++)

using namespace std;

map<int,int,greater<int> > mp;
int g;
stack<int> stk;

void factor(vector<int> &a , int n , int min)
{
	int i;
	for ( i = min ; i <= n/2 ; i++)
	{
		if( n%i == 0 )	a.push_back(i);
	}
	a.push_back(n);
}

bool dfs(int goal,int m)
{
	bool flag;
	map<int, int,greater<int> >::iterator ite; 
	if( goal == 0 )
	{
		//搜索完成
		if( m == 1 )	return true;
		else{	//深入
			m--;
			goal = g ;
			flag = dfs(goal,m);
			if(flag)	return true;
			else
				return false;
		}
	}	
	else
	{
		if( !stk.empty() && goal != g )
			ite = mp.find(stk.top());
		else
			ite = mp.begin();
		for (; ite != mp.end() ; ite++)
		{
			//对每个数据进行判断。
			if( goal >= ite->first && ite->second > 0 )
			{
				//可用
				ite->second--;
				stk.push(ite->first);
				if(dfs(goal-ite->first,m))	return true;
				else
				{
					ite->second++;
					stk.pop();
					//top--;
					if( goal == g )	return false;
				}
			}
		}
		return false;
	}
}

int main()
{
	int goal,i,t,n,m,x,sum;
	map<int,int,greater<int> > temp;
	vector<int> a;
	cin>>n;
	while ( n != 0 )
	{
		//sum存储所有数据和，mp存储各数据及其出现次数，按大到小保存，a保存候选数据goal
		a.clear();
		mp.clear();
		sum = 0 ;
		REP(i,n)
		{
			cin>>t;
			sum += t;
			mp[t]++;
		}
		factor(a,sum,mp.begin()->first);
		temp = mp;
		REP(i,a.size()-1)
		{
			//最后一个为和,数据中每个为候选数据
			m = sum/a[i];
			goal = a[i];
			g = goal;
			//需要m次为a[i]长度的木棍
			if(dfs(goal,m))	//搜索成功
			{
				cout<<a[i]<<endl;
				break;
			}
			//回复map
			mp = temp;
		}
		if( i == a.size()-1 )	cout<<a[a.size()-1]<<endl;
		cin>>n;		
	}
	return 0;
}

• Re:数据很水。简单剪枝即可。贴个代码参考。 (2019) stu_20090658 2011-05-05 11:54:27