【编程题目】有两个序列 a,b，大小都为 n,序列元素的值任意整数，无序；（需要回头仔细研究）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

32.（数组、规划）
有两个序列 a,b，大小都为 n,序列元素的值任意整数，无序；
要求：通过交换 a,b 中的元素，使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2,3];
var b=[1,2,3,4,5,40];

首先，目标一定是先找到n个数字，使得数字和比总和的一半小，但是最接近。

思路一：开始看这道题跟之前学的动态规划很像，就想用动态规划来解。但是....做不出来........... 必须要选一半的数字让我头都大了。

思路二：接着想写递归，就是把a, b（各n个）中的数字都放在 c 中，选一半的数字n个那就可以分为：

1.选入最后一个数字第2n - 1个，在剩下的数字中选择其他 n - 1个数字

2.不选入最后一个数字，在剩下的数字中选择 n个数字

这样，递归的思路就有了。

可是在怎么把得到的结果传出来上面我又犯了难，每个数字都是一层层递归选的，怎么传出来啊？？好了，到这里卡死了......

void choose(int * c, int len, int N, int sum) //N是要从中挑选几个数字
{
static int sumtmax = ;
static int sumt = ;
static int num = ;
if(len < N)
{
return;
}
if(N == )
{
if(sumt <= sum/ && sumt > sumtmax)
{
sumtmax = sumt;
}
printf("%d : %d %d\n", ++num, sumt, sumtmax);
return;
} choose(c, len - , N, sum); sumt += c[len - ];
choose(c, len - , N - , sum);
sumt -= c[len - ];
}void exchange(int * a, int * b, int len)
{
int * c = (int *)malloc( * len * sizeof(int));
int * smaller = (int *)malloc(len * sizeof(int));
int sum = ;
for(int i = ; i < len; i++)
{
c[i] = a[i];
sum += a[i];
}
for(int i = ; i < len; i++)
{
c[i + len] = b[i];
sum += b[i];
} choose(c, len * , len, sum);}

思路三：和12个人排两列的思路相同。用二进制用数字i 从0 - （1 << 2 * n）的范围变化，其二进制中的1，就表示数字选入a, 我们遍历所有的可能找到a中的和最接近总和一半的组合。再另外用一个数字保存最接近时的分布就好了。

不过这样的写法一个很不好的限制就是int的位数是有限的，只有64位，也就是说n大于32时我的方法就失效了

/*
32.（数组、规划）
有两个序列 a,b，大小都为 n,序列元素的值任意整数，无序；
要求：通过交换 a,b 中的元素，使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2,3];
var b=[1,2,3,4,5,40];
*/#include<stdio.h>
#include<stdlib.h>
#include<string.h>int bit_c(int n) //统计n的二进制表达中有几个1
{
int result = ;
for(; n; n &= n-, result++);
return result;
}void exchange2(int * a, int * b, int len)
{
int * c = (int *)malloc( * len * sizeof(int));
int * smaller = (int *)malloc(len * sizeof(int));
int sum = ;
for(int i = ; i < len; i++)
{
c[i] = a[i];
sum += a[i];
}
for(int i = ; i < len; i++)
{
c[i + len] = b[i];
sum += b[i];
} int maxsumh = ;
int mask = ;
for(int i = ; i < ( << len * ); i++)
{
if(bit_c(i) == len)
{
int sumhalf = ;
for(int j = ; j < len * ; j++)
{
if(((i >> j) & ) == )
{
sumhalf += c[j];
}
}
if(sumhalf <= sum / && sumhalf > maxsumh)
{
maxsumh = sumhalf;
mask = i;
}
}
} int ai = , bi = ;
for(int j = ; j < len * ; j++)
{
if(((mask >> j) & ) == )
{
a[ai++] = c[j];
}
else
{
b[bi++] = c[j];
}
} printf("最小差值为：%d", sum - * maxsumh); free(c);}int main()
{
int a[] = {,,,,};
int b[] = {, , , , };
exchange2(a, b, );
return ;
}