程序1：（程序算法错）
基本思想：只要可以在两组中找到可以使得交换后差值缩小的数，就交换之。直至不存在这样的数。程序如下
#include <iostream>
using namespace std;

void Proc(int num)
{
	int i,j;
	int a[101],w1(0),w2(0);
	for(i=0; i<num; i++)
		cin>>a[i];
	for(i=0; i<num/2; i++)
		w1 += a[i];
	for(; i<num; i++)
		w2 += a[i];
	bool flag(0);
	for(; !flag; )
	{
		flag = true;
		for(i=0; i<num/2; i++)
			for(j=num/2; j<num; j++)
				if( abs(w1-a[i]+a[j]-(w2-a[j]+a[i])) < abs(w1-w2) )
				{
					flag = false;
					w1 = w1-a[i]+a[j];
					w2 = w2+a[i]-a[j];
					int tmp = a[i];
					a[i] = a[j];
					a[j] = tmp;
				}
	}
	if( w1 > w2 )
		cout<<w2<<' '<<w1<<endl;
	else
		cout<<w1<<' '<<w2<<endl;
}

int main()
{
	int num; 
	for(; cin>>num; )
		Proc(num);
	return 0;
}
我认为即使任意两个数交换不能使得差值减少仍不能判断当前是最优方案。因为可能找出几个数为一组交换一组后使得差值缩小。如下面数据这个程序给出了错误的解答。
8
99 40 3 10 70 70 7 7

程序二：随机算法
#include <iostream>
#include <cmath>
using namespace std;

void in(int n,int a[],int& s)
{
	for(int i=s=0;i<n;++i)
		cin>>a[i],s+=a[i];
}

int main()
{
	int a[64],b[64],sa,sb,n,i,j,an,bn,t,d1,d2;
	cin>>n;
	an = n/2;
	bn = n-an;
	in(an,a,sa);
	in(bn,b,sb);
	for(t=0;t<250;++t)
	{
		i = rand()%an;
		j = rand()%bn;
		d1 = abs(sa-sb);
		d2 = abs(sa-sb-(a[i]-b[j])*2);
		if(d1 >= d2)
		{
			sa -= a[i] - b[j];
			sb -= b[j] - a[i];
			int temp = a[i];
			a[i] = b[j];
			b[j] = temp;
		}
	}
	if(sa<sb)
		cout<<sa<<" "<<sb;
	else
		cout<<sb<<" "<<sa;
	cout<<endl;
	return 0;
}
这个程序逻辑上也有错误，但是也AC了而且是0MS， 28K。

• 你帮忙加几个 (1690) sunmoonstar_love 2005-08-22 14:59:48
• 说得对呀 (31) ACM05002 2005-08-23 22:40:21