1. a = c , b = c
2. 按照suma>sumb, 取剩下的最大的给b，最小的给a； 反之最大的给a，最小的给b。
程序如下：
#include <stdio.h>
#include <stdlib.h>
static int
intcompare(const void *p1, const void *p2)
{
int i = *((int *)p1);
int j = *((int *)p2);
if (i > j)
return (1);
if (i < j)
return (-1);
return (0);
}
int change(int *a, int *b, int size)
{
int *c = (int*) malloc(2*size);
int pos_a,pos_b,pos_c,pos_cend;
int sum_a,sum_b;
int i;
memcpy(c, a, sizeof(int)*size);
memcpy(c+size, b, sizeof(int)*size);
qsort((void *)c, 2*size, sizeof (int), intcompare);
pos_a=pos_b=pos_c=0;
pos_cend = 2*size-1;
a = c;
b = c;
sum_a = a;
sum_b = b;
while (pos_cend > pos_c ) {
if (sum_a > sum_b) {
a = c;
b = c;
sum_a += a;
sum_b += b;
} else {
a = c;
b = c;
sum_a += a;
sum_b += b;
}
}
}
int main (int argc, char **argv)
{
int a= {1, 2, 3,4,5,6};
int b= {7, 8, 9,10,11,12};
int i;
change(a,b,6);
printf("a=");
for(i=0; i <6; i++)
printf("%d,",a);
printf("\n");
printf("b=");
for(i=0; i< 6; i++)
printf("%d,", b);
printf("\n");
} 当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b - （sum(b) - b + a)
= sum(a) - sum(b) - 2 (a - b)
= A - 2 (a - b)
设x = a - b
|A| - |A'| = |A| - |A-2x|
假设A > 0,
当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,
如果找不到在(0,A)之间的x，则当前的a和b就是答案。
所以算法大概如下：
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。
[ 本帖最后由 xmyth 于 2006-11-14 20:45 编辑 ] xmyth 快四年一贴啊.
你说的我看懂了 原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b - （sum(b) - b + a)
= sum(a) - sum(b) - 2 (a - b) ...
想法很好呀，又有数学证明，但是什么时候会
找不到（0,A）之间的x呢？
比如：
1，2，3，4，5，12
最佳方案好像是：
4，5，3
1，2，12
那么0<（3－2）<(15-12)
好像不行呀？
是不是要改进一下结束的条件？
我考虑的对不对？
高手看看！
谢谢！！ 这个结束条件应该是没有问题的
在你说的这个例子里，已经满足了我所提出的结束条件
前面我假设了A>0 (如果A不大于0，对换一下就好了)
所以这里a = {1,2,12}; b = {4,5,3};
x=a-b
所有的x应该都不能满足（0, 3)的条件了，所以满足结束条件了。 真的只有八分钟吗？字都打不完啊。 原帖由 xmyth 于 2006-11-14 20:44 发表
这个结束条件应该是没有问题的
在你说的这个例子里，已经满足了我所提出的结束条件
前面我假设了A>0 (如果A不大于0，对换一下就好了)
所以这里a = {1,2,12}; b = {4,5,3};
x=a-b
所有的x ...
我一眼就感觉你那公式很可能是对的
这种类似的题很多的
比如100个红包，7个人分，怎么分才最均匀，是不是更头疼？
我也来出个题
:lol: 用二重循环把a中的每个元素和b中的每个元素逐个“尝试交换”，如果是差值变小就维持交换，否则就交换回去，也就是不交换，
每有一次交换，“尝试交换”的二重循环就重新从头开始，
直到没有任何交换使差值变小为止。
这种方法不是很简洁，但的确是可行的。
前边贴出代码的算法，有过一次交换后，循环没有从头开始，所以是错误的。例如a和b交换后，b中的元素改变了，不能再保证a和b[ i ]交换不会使差值变小，这时循环必须从头开始。
#include <stdio.h>
#include <math.h>
#define N 10
void ary_init(int a[], int b[]){ //初始化数组
int i;
for (i=0; i<N; i++){
a = rand()%10000;
}
for (i=0; i<N; i++){
b = rand()%100;
}
return;
}
long sum(int a[]){ //数组求和
int i;
int s;
for (s=0,i=0; i<N; i++){
s += a;
}
return s;
}
void change(int *a, int *b){ //数组元素交换
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
return;
}
void prt_ary(int a[], int b[]){ //列印两数组元素及各自元素和
int i;
for(i=0; i<N; i++){
printf("%5d ", a);
}
printf("\n");
for(i=0; i<N; i++){
printf("%5d ", b);
}
printf("\n");
printf("%d\n", sum(a));
printf("%d\n", sum(b));
}
int slove(int a[], int b[]){
int i;
int j;
int is_swap = 0;//是否修交换过数据标志
int ab_diff;
ab_diff = abs(sum(a)-sum(b));
for (i=0; i<N; i++){
for (j=0; j<N; j++){
change(a+i, b+j);
if (abs(sum(a)-sum(b)) < ab_diff){//判断是否需要交换元素
is_swap = 1; //置位交换标志
ab_diff = abs(sum(a)-sum(b)); //更新差值
}
else{
change(b+j, a+i);//不交换
}
}
}
return is_swap;
}
int main(){
int a;
int b;
ary_init(a,b);//数组元素初始化
prt_ary(a, b);//列印当前数组状态
while (slove(a, b));//处理数组
prt_ary(a, b);//列印交换后数组状态
getch();
}
[ 本帖最后由 greensky_34 于 2006-11-14 21:20 编辑 ] 原帖由 xmyth 于 2006-11-14 20:44 发表
这个结束条件应该是没有问题的
在你说的这个例子里，已经满足了我所提出的结束条件
前面我假设了A>0 (如果A不大于0，对换一下就好了)
所以这里a = {1,2,12}; b = {4,5,3};
x=a-b
所有的x ...
哦，明白了，如果(sum(a) - sum(b)) > (a -b) > 0的话，也就是数组a的和比数组b的和大，
而数组b中有比数组a中小的元素，如果把a和b交换，就可以把数组a和数组b的差缩小，又因为
(sum(a) - sum(b)) > (a -b) ，所以交换后不会出现sum(a) < sum(b)的情况。这样循环调整后，
当整体上sum(a)> sum(b))时，局部上（数组元素）无法交换了，也就是无法找到符合条件的x了。
呵呵，本人天生比较笨，要想一想才能明白！
谢谢xmyth的解释！