类似的题目，我总是用回溯，结果总是 TLE，请教高手，应该怎么做。

#include "iostream.h"

#define max 6

int graph[max];
int map[max];
int total;		//总和，加权后

bool check()
{
	int i;
	int t = 0;
	for( i = 0 ; i < max ; i++ )
		t += ( i + 1 ) * map[i];
	if( t == total / 2 )
		return true;
	else
		return false;
}

int main()
{
	int i;
	int sum;		//个数
	bool flag;
	int top;
	int caseCount = 0;
	
	sum = 0;
	total = 0;
	for( i = 0 ; i < max ; i++ )
	{
		cin >> graph[i];
		sum += graph[i];
		total += ( i + 1 ) * graph[i];
	}
	while( sum > 0 )
	{
		caseCount++;
		cout<<"Collection #"<<caseCount<<":"<<endl;
		if( total % 2 == 0 )
		{
			for( i = 0 ; i < max ; i++ )
				map[i] = -1;
			top = 0;
			flag = false;//没有找到分法
			do
			{
				map[top]++;
				if( map[top] > graph[top] )
				{
					map[top] = -1;
					top--;
				}
				else
				{
					if( top == max - 1 )
					{
						if( check() )
						{
							cout<<"Can be divided."<<endl;
							flag = true;
						}
					}
					else
					{
						top++;
					}
				}
			}while( top >= 0 && !flag );
			if( !flag )
				cout<<"Can't be divided."<<endl;
		}		
		else
		{
			cout<<"Can't be divided."<<endl;
		}
		cout<<endl;
		//==================================
		//下一循环
		sum = 0;
		total = 0;
		for( i = 0 ; i < max ; i++ )
		{
			cin >> graph[i];
			sum += graph[i];
			total += ( i + 1 ) * graph[i];
		}
	}
	
	return 0;
}

• 不能搬1011的办法啊，那么大的规模肯定超时的 (1619) frkstyc 2005-05-27 11:35:51
• 可以直接动态规划，也可以用zhucheng的结论 (0) WZPWZPWZP 2005-05-27 11:41:59
  • 奇怪的是降规模之后我用knapsack做怎么都不对，最后搜出来的 (0) frkstyc 2005-05-27 11:43:53
    • 那就不清楚了，不过那么多0MS的，应该是等价降规模的吧 (0) WZPWZPWZP 2005-05-27 12:02:46
      • 看我贡献多多wa+re+mle+tle (0) frkstyc 2005-05-27 12:04:44