问题描述：
有两个整数序列a, b，大小都为n, 序列元素的值任意整数，无序。
要求：通过交换a, b 中的元素，使得sum(a)-sum(b)，差最小。
例如:
var a=[80, 40, 60, 10, 20, 30];
var b=[10, 20, 50, 40, 30, 20];
分析：
近似最优算法：
当前数组a和数组b的和之差为：A = sum(a) – sum(b)，a的第i个元素和b的第j个元素交换后，a和b的和之差为：
A’ = (sum(a) – a[i] + b[j]) – (sum(b) – b[j] + a[i])
= sum(a) – sum(b) – 2 (a[i] – b[j])
= A – 2 (a[i] – b[j])
设x= a[i] – b[j]，A’ = A-2x，只要 0 < x <= A/2，则A’ < A。
所以，目标就是寻找i和j，使得x在0和A/2之间，并且越接近A/2越好。直到找不到这样的x为止。
当前数组a和数组b的和之差为：A = sum(a) – sum(b)，a的第i个元素和b的第j个元素交换后，a和b的和之差为：
A’ = (sum(a) – a[i] + b[j]) – (sum(b) – b[j] + a[i])
= sum(a) – sum(b) – 2 (a[i] – b[j])
= A – 2 (a[i] – b[j])
设x= a[i] – b[j]，A’ = A-2x，只要 0 < x <= A/2，则A’ < A。
所以，目标就是寻找i和j，使得x在0和A/2之间，并且越接近A/2越好。直到找不到这样的x为止。
代码实现：
// 32.cc
#include <iostream>
using namespace std; // 计算数组的和
int sum(const int* a, int n) {
int count = ;
for (int i = ; i < n; i++)
count += a[i];
return count;
} // 交换数组元素得到平衡集
void balance_swap(int* a, int* b, int n) {
// a指向和比较大的集合
if (sum(a, n) < sum(b, n)) {
int* t = a;
a = b;
b = t;
} bool loop = true;
while (loop) {
loop = false;
for (int i = ; i < n; i++) {
for (int j = ; j < n; j++) {
int diff = a[i] - b[j];
int A = sum(a, n) - sum(b, n);
if (diff > && diff < A / ) {
loop = true;
int tmp = a[i];
a[i] = b[j];
b[j] = tmp;
}
}
}
}
} // 打印数组元素
void print(const int* a, int n) {
for (int i = ; i < n; i++)
cout << a[i] << " ";
cout << endl;
} int main() {
int a[] = {, , , , , };
int b[] = {, , , , , };
int n = sizeof(a) / sizeof(int); balance_swap(a, b, n); print(a, n);
print(b, n); return ;
}
输出：
$ ./a.exe