#include <iostream>
using namespace std;

#define MAXN 200
#define MAXM 20

int value[2][MAXN];		//value[0]-prosecution, value[1]-defence
bool used[MAXN];	//mark whether the jury i is being used
int result[MAXM];	//record the result index
int m,n,diffAbs, sum;

void SetResult()
{
	for(int i(0),j(0); i<n&&j<m; ++i)
		if(used[i]) result[j++]=i;
}

void Print()
{
	int p(0), d(0);
	for(int i(0); i<m; ++i)
	{
		p+=value[0][result[i]];
		d+=value[1][result[i]];
	}
	cout <<"Best jury has value " << p <<" for prosecution and value "
		<< d <<" for defence: " <<endl; 
	for(int i(0); i<m; ++i)
		cout << result[i]+1 <<" ";
	cout <<endl;
}

void DFS(int curDiff, int curSum, int index, int count)
{
	if(count==m)
	{
		if((abs(curDiff)<diffAbs)||(abs(curDiff)==diffAbs && curSum>sum))
		{
			diffAbs=abs(curDiff);
			sum=curSum;
			SetResult();
		}
		return;
	}
	if(n-index+count<m) return;

	for(int i(index); i<n; ++i)
	{
		used[i]=true;
		DFS(curDiff+value[0][i]-value[1][i], curSum+value[0][i]+value[1][i], i+1, count+1);
		used[i]=false;
	}
	return;
}

int main()
{
	int round(0);
	while(++round)
	{
		cin>>n>>m;
		if(!m && !n) break;
		//assert(m<=n);
		for(int i(0); i<n; ++i)
			cin>>value[0][i]>>value[1][i];
		diffAbs=40*m+1;
		sum=-1;

		memset(used, false, sizeof(used));
		DFS(0,0,0,0);
		cout << "Jury #" << round << endl;
		Print();
		cout <<endl;
	}
		return 0;
}

• Re:DFS算法，十分简单，可惜TLE了~~~谁有兴趣看看怎么剪枝 (53) lovepal4 2012-02-27 11:58:47