c = a - b
两个数组的差值delt
将delt与c比较，小于则更换
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define NUM200
#define LIMIT 1000000
struct sign{
int a;
int b;
int delt;
};
int main(void){
srand(time(NULL));
int a[NUM];
int b[NUM];
int c[NUM][NUM];
int i, j;
int delt = 0;
int temp;
struct sign s;
s.a=0; s.b=0; s.delt=0;
for(i=0; i<NUM; i++)
{
a[i] = (rand())%LIMIT;
b[i] = (rand())%LIMIT;
delt +=(a[i] - b[i]);
printf("a is %i; b is %i; delt is %i\n", a[i], b[i], delt);
}
for(i=0; i<NUM; i++)
for(j=0; j<NUM; j++)
{
c[i][j] = a[j] - b[i];
}
s.delt = delt;
if(delt == 0)
return 0;
for(i = 0; i<NUM; i++)
{
printf("%5.i", a[i]);
}
printf("\n");
for(i = 0; i<NUM; i++)
{
printf("%5.i", b[i]);
}
printf("\n");
while(1)
{
for(i=0; i<NUM; i++)
for(j=0; j<NUM; j++)
{
temp = s.delt - 2*c[i][j];
if( abs(temp) < abs(delt) && abs(temp)< abs(s.delt) )
{ s.a = j;
s.b = i;
s.delt = temp;
}
}
if(delt == s.delt)
break;
delt = s.delt;
printf("delt is %i\n", delt);
temp = a[s.a];
a[s.a] = b[s.b];
b[s.b] = temp;
if(delt == 0)
break;
for(i=0; i<NUM; i++)
{
c[i][s.a] = a[s.a] - b[i];
c[s.b][i] = a[i] - b[s.b];
}
}
int tempa=0, tempb=0;
for(i = 0; i<NUM; i++)
{
printf("%5.i", a[i]);
tempa += a[i];
}
printf("%10.i\n",tempa);
for(i = 0; i<NUM; i++)
{
printf("%5.i", b[i]);
tempb += b[i];
}
printf("%10.i\n", tempb);
printf("delt is %i", delt);
return 0;
}
[ 本帖最后由 tianshanxue2005 于 2007-8-29 18:56 编辑 ]
呵呵，还能跟贴么
想到一个方法，因为是求和，其实无所谓负数还是正数，没有关系。我的办法是：
两个数组和得差要最小，理想的情况就是sum(a)=sum(b)；而2N个数的和为total=sum(a)+sum(b)，求其算术平均为avg=total+1/2N。同理，avgab=total+1/2，这是a,b的各自和的理想值。其实，选取的策略就是使调整后的sum(a)=sum(b)=avgab。
采取这样地选取算法：
1）从2N-k个数中取出与avg的差的绝对值最小的整数，作为ak。其中,k为已经选出的a中的元素的个数。
2）重新计算avgab=avgab-ak，（total前面已经计算了，所以这里不用再算了，直接使用就可以了）。同时计算avg = avgab+1-a1/N-k，然后再重复1）。
3）直道选出N个数，选出的数作为a中元素，剩下的数即是数组b中的元素了。
很明显的是，理想情况下，这样选出来的sum(a)=sum(b)。在非理想情况下，这样选出来的也是满足条件的a和b。
[ 本帖最后由 NewCore 于 2007-8-30 00:24 编辑 ] 所有用了“排序”的都应该是错的。
求和只要开始时做一遍，以后随时订正。
遍历两个数组的元素，如果交换能降低两个数组和之差，就交换，同时订正数组和。
如此反复，直到任何这样两个不同数组的元素交换都只能增加或不改变数组和之差。
[ 本帖最后由 tom_xx_hu@yahoo 于 2007-8-30 02:14 编辑 ] 首先整体排序，然后两个数组分别成对交替前后顺序的取数。不置可否。 我贴一个,当数目比较小的时候运行还比较快.
在VC中开发.
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include "Windows.h"
void quicksort(int *p, int from ,int to)
{
int i,j,pivot,temp;
if(from >= to)
{
return;
}
i = from + 1;
j = to;
pivot = *(p + from);
while(i <= j)
{
while (*(p + i) <= pivot)
{
i++;
}
while(*(p + j) > pivot)
{
j--;
}
if(i < j)
{
temp = *(p+i);
*(p+i) = *(p+j);
*(p+j) = temp;
}
}
temp = *(p+j);
*(p+j) = pivot;
*(p+from)=temp;
quicksort(p,from,j-1);
quicksort(p,j+1,to);
}
//高位右移时，低位向左移动
void move_left_zero(int *p, int num)
{
int i,j,n;
if(num == 0)
{
return;
}
for(i = 0; i < num-1; i++)
{
if((*(p+i) == 0) &&(*(p+i+1) == 1))
{
break;
}
}
if( i == num-1)
{
}
else
{
for(j = 0; j < num-1-i; j++)
{
*(p+j) = *(p+j+i+1);
}
for(n = 0; n < i+1; n++)
{
*(p+j+n) = 0;
}
}
return ;
}
int combine_incre(int *p, int num)
{
int i;
for(i = 0; i < num-1; i++)
{
if((*(p+i) == 1) && (*(p+i+1) == 0))
{
*(p+i) = 0;
*(p+i+1) = 1;
move_left_zero(p,i);
break;
}
}
if(i == num-1)
{
return false;
}
else
{
return true;
}
}
void prepare_combine(int **p, int size, int num)
{
int i;
*p = (int*)malloc(size*sizeof(int));
memset(*p,0,size*sizeof(int));
for(i = 0; i < num ;i++)
{
*(*p + i) = 1;
}
}
//size = 12;
//测试组合数运行，组合
int combine_test(int size,int num)
{
int i;
int count = 0;
int *p;
prepare_combine(&p,size,num);
count++;
for(i = 0; i < size; i++)
{
printf("%d,",p);
}
printf("\r\n");
while(combine_incre(p,size))
{
count++;
for(i = 0; i < size; i++)
{
printf("%d,",p);
}
printf("\r\n");
}
return 0;
}
int main(int argc, char* argv[])
{
int i,size;
int a;
long midsum;
long minsum;
long temp;
int count = 0;
int *p;
int *result;
size = 30;
for(i = 0; i < size; i++)
{
a = rand();
Sleep(100);
}
temp = minsum = midsum = 0;
quicksort(a,0,size-1);
for(i = 0; i < size-1; i++)
{
printf("%d,",a);
}
printf("\r\n");
//combine_test(size,size/2);
prepare_combine(&p,size,size/2);
prepare_combine(&result,size,size/2);
count++;
for(i = 0; i < size; i++)
{
if(*(p+i) == 1)
{
minsum += a;
}
midsum += a;
}
midsum /= 2;
printf("the min sum is:%d; mid sum is:%d\r\n",minsum,midsum);
while(combine_incre(p,size))
{
temp = 0;
for(i = 0; i < size; i++)
{
if(*(p+i) == 1)
{
temp += a;
}
}
if(temp == midsum)
{
for(i = 0; i < size; i++)
{
result = p;
}
break;
}
else if(temp < midsum)
{
if(temp > minsum)
{
minsum = temp;
for(i = 0; i < size; i++)
{
result = p;
}
}
}
}
printf("the sum is:%d:",minsum);
for(i = 0; i < size; i++)
{
printf("%d,",result);
}
printf("\r\n");
getchar();
return 0;
} 从头到尾看了一遍，赞同zwylinux，tom_xx_hu的方法。看了xmyth的推理让我想起了高中的数学，很有味道，十几年都没有感受了。 原帖由 namtso 于 2006-11-13 17:16 发表 http://bbs.chinaunix.net/images/common/back.gif
我相信，这个题在8分钟内能写出代码来的人，绝对是大大的牛人。
我觉得应该这样：
a和b 分别求出累加和，得出累加和的差c1，然后循环查找找a中的某个元素a，使得a与b中的某个元素b交换之后，得出一个新的 ...
我也是这个想法。顶个 单一的元素交换很多时候不是最优的,
如果出现这种情况,有可能两个元素一起交换,导致两组数的差最小.
因此最优的情况,应该是从2n个数中取n个数,进行穷举. 原帖由 omiga2 于 2007-9-13 19:57 发表 http://bbs.chinaunix.net/images/common/back.gif
从头到尾看了一遍，赞同zwylinux，tom_xx_hu的方法。看了xmyth的推理让我想起了高中的数学，很有味道，十几年都没有感受了。
不容易。4年3帖，一帖顶了在下（当然还有zwylinux），荣幸之至。
3帖得11分，按平均每帖得分衡量，在CU一定名列前茅。赞！