1011.txt

推荐pku_1011上的好题

回溯算法，基本上就是：
追一个MM，但也许你还是情窦初开的新手，不知道如何才能讨得MM的欢心，于
是你只好一条路一条路的试，MM不开心了，你就回溯回去换另一种方式。当然
其间你也许会从某些途径得到一些经验，能够判断哪些路径不好，会剪枝（这
就是分支估界了）。你也可以随机选择一些路径来实施，说不定能立杆见影（
这就是回溯的优化了）但总的来说，你都需要一场持久战。。。。
该算法一般也能得到最优解，因为大多数MM会感动滴！！但其缺点是开销大！
除非你是非要谈一场恋爱不可，否则不推荐使用。特别是你可能还有许多其他
的事情要做，比如学习，比如事业。。。。

下面是pku1011绝对经典的DFS+剪枝的利用了回溯的思想好题的算法。
值得大家去学习和研究下，怎样剪枝效果最好。


#include <iostream>
//#include <fstream>
using namespace std;
int flag = 0;
int lay = 0;
int l[100];
int a[100];
int Qsort( int t[], int start, int end )
{
	int i;
	t[0] = t[start];
	i = 0; // i==0表示t[up]跟t[0]比较， i==1表示t[down]跟t[0]比较。
	int up = end;
	int down = start;
	while ( up != down )
	{
		if ( i == 0 && t[up] <= t[0] )
		{
			up--;
			continue;
		}
		if ( i == 0 && t[up] > t[0] )
		{
			t[down] = t[up];
			i = 1;
			down++;
			continue;
		}
		if ( i == 1 && t[down] >= t[0] )
		{
			down++;
			continue;
		}
		if ( i == 1 && t[down] < t[0] )
		{
			t[up] = t[down];
			i = 0;
			up--;
		}
	}
	t[down] = t[0];
	return down;
}
void qs ( int t[], int start, int end )		//递归实现快排
{
	int mid;
	if ( start < end )
	{
		mid = Qsort(t,start,end);
		qs ( t,start,mid-1);
		qs ( t,mid+1,end);
	}
}
int f ( int t, int sum, int position, int max, int n )
{
	if ( t == sum )
	{
		if ( max-sum == sum )
		{
			flag = 1;
			return 1;
		}
		position = 1;
		while ( l[position] == 1 && position <= n )
			position++;
		if ( position > n )
			return 0;
		l[position] = 1;
		f ( a[position], sum , position+1, max-sum,n);
		l[position] = 0;
	if ( max-sum == sum )
		flag = 1;
	//	if ( flag == 1 )
	//		return 1;

	}
	else
	{
		int pos = position;
		while ( a[pos] + t > sum || l[pos] == 1 )
		{
			pos++;
			if ( pos > n )
				break;
		}
		if ( pos > n )
			return 0;
		position = pos;
		t+=a[position];
			if (a[position] != a[position-1])
			{
				l[position] = 1;
				f(t,sum,position+1,max,n);
				l[position] = 0;
			}
			else if (l[position-1] == 1)
			{
				l[position] = 1;
				f(t,sum,position+1,max,n);
				l[position] = 0;
			}
		if ( flag == 1 )
			return 1;
		
		if ( t != sum )
		{
			l[position] = 0;
			t -= a[position];
			f(t,sum,position+1,max,n);
		}
	}
	
	return 1;
}
int main ()
{
//	ofstream fop ("out.txt");
	int n,i;
	int sum;
	while ( scanf("%d",&n) && n!=0 )
	{
		for ( i = 1; i <= n; i++ )
			l[i] = 0;
		sum = 0;
		for ( i = 1; i <= n; i++ )
		{
			scanf("%d",&a[i]);
			if ( a[i] > 50 )
			{
				i--;
				n--;
				continue;
			}
			sum += a[i];
		}
		if ( n == 1 )
		{
	//		fop<<a[1]<<endl;
	//		flush(cout);
			cout<<a[1]<<endl;
			continue;
		}
		qs(a,1,n);
		a[0] = -1;
		for ( i = 1; i < 100; i++ )
			l[i] = 0;
		l[0] = 1;
		for ( i = a[1]; i<=(sum+1)/2; i++ )
		{
			if ( sum%i==0)
			{
				f(0,i,1,sum,n);
				if ( flag == 1 )
					break;
			}
		}
		if ( flag == 1 )
	//		fop<<i<<endl;
			cout<<i<<endl;
		else
//			fop<<sum<<endl;
			cout<<sum<<endl;
//		flush(cout);
		flag = 0;
		
	}
	return 1;
}