一个2n的整数数组，现要分成个数相等的两组，每组 n 个整数。

设计算法，保证两组和之差的绝对值最小

先把这个数求和 再除2 得到的两个数 然后while循环 拿一个数随机取n个数 这n个的和相加等于这个数 再对另个数取n个数 遇到和前面相同的重取 看有没有这n个 没有就重新循环 有就跳出

不知道能不能实现 有点笨 这办法 我也想不出 呵呵

I think this problem is an NPC

1楼说的头一句应该没错，首先确定平均值。然后的分配就是一个典型的组合优化问题，好像真的是NP难的

补充一点，如果效率优先、并只求近似解的话，可以有一个O(n^2)的算法。

for(i=0;i<2n;i+=2)
{
以当前值为标准，在剩余的数组中（第一次循环时则是全数组）找到与其值最近的元素；
将两元素分别放入两子数组；(在不加大复杂度的前提下，可以稍微提高点精度，就是若上一次子数组a的值小的话，本次循环则把大值放入a)
}

当然，这是一种典型的贪心算法思想，只能得到近似解。要得到精确解的话，应该是个NP-hard问题

这样不知道行不行：
1.先把两组数的和求出来进行比较，得出这两组数的和的差值A1，
2.再在两个数组中分别找到一个数，使它们的差小于A1，对他们进行调换.
3.重复1，2步的操作直到找不到满足条件的数

楼上的算法理论上可以得到精确解，但是也是一个NP难的算法。呵呵，典型的穷举嘛

这有一种思想：不停的交换两部分之间的元素，使得这两部分之间的和之差越来越小。



#include<stdio.h>
#include<math.h>
#include<stdlib.h>

void change(int *x, int * y)
{
int temp=*x;
*x=*y;
*y=temp;
}

int main()
{
int a[4]=
{
4,2,3,6
};
int b[4]=
{
10,11,15,19
};

int i,j;
int sumA=0;
int sumB=0;

for(i=0;i<4;i++)
{
sumA+=a[i];
sumB+=b[i];
}

int ab_diff=abs(sumA-sumB);

for (i=0; i<4; i++)
{
for (j=0; j<4; j++)
{
sumA=sumA-a[i]+b[j];
sumB=sumB+a[i]-b[j];
if ( abs(sumA-sumB) > ab_diff )
{
sumA=sumA+a[i]-b[j];
sumB=sumB-a[i]+b[j];
}
else
{
change(a+i, b+j);
ab_diff = abs(sumA-sumB); //更新差值
}
printf("%d,%d\n",sumA,sumB);
}
}

for(i=0;i<4;i++)
{
printf("%d ",a[i]);
}

printf("\n");

for(i=0;i<4;i++)
{
printf("%d ",b[i]);
}

return 1;

}