如何交换两个等长整形数组使其数组和的差最小（C和java实现）

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100
int A[N];
int B[N];
//随机初始化一个数组
void init(int a[], int n)
{
int i;
for(i = ; i < n; ++i)
a[i] = rand() % N;
}
//输出数组
void print(int a[], int n)
{
int i;
for(i = ; i < n; ++i)
printf("%d ", a[i]);
printf("\n--------------------------------------------\n");
} //求数组和
int sum(int a[], int n)
{
int i, sum = ;
for(i = ; i < n; ++i)
sum += a[i];
return sum;
}
//交换整数
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//n1,n2为数组A和B中实际初始化的元素个数
int solve(int n1, int n2)
{
int i, j; //循环迭代变量
int x, y; //用于保存可交换数字对的索引
int maxSum, minSum; //分别用于保存两个数组的数字之和
int diff; //diff = sum1 - sum2
int maxdiff; // 2 * (A[x] - B[y])
int flag; //标记是否找到可交换的数字对
int temp;
int *pMax; //指向数字总和较大的数组
int *pMin; //指向数字总和较小的数组 //随机初始化数组
init(A, n1);
init(B, n2);
print(A, n1);
print(B, n2);
//求数组中数字之和
maxSum = sum(A, n1);
minSum = sum(B, n2); if(maxSum == minSum)
{
printf("There is no need to swap!\n");
return ;
} //令pMax和pMin分别指向数字总和大的数组以及总和小的数组
pMax = A;
pMin = B;
if(maxSum < minSum)
{
pMax = B;
pMin = A;
swap(&maxSum, &minSum);
}
//循环交换两个数组中的数字对，在交换的过程中，始终
//保持pMax数组的数字总和大于或者等于pMin数组的数字总和。
//也就是保持diff >= 0
diff = maxSum - minSum;
while()
{
flag = ;
x = y = ;
maxdiff = ;
//寻找能够使diff减小的数字对。
//从趋势上来看，
//减小的幅度越大diff收敛的越快,
//while循环的次数也越少
for(i = ; i < n1; ++i)
{
for(j = ; j < n2; ++j)
{
temp = pMax[i] - pMin[j];
if(temp > && (diff - * temp) >= )
{
if(maxdiff < *temp)
{
maxdiff = * temp;
x = i;
y = j;
flag = ;
}
}
}
}
if(flag) //找到了可以使diff减小的数字对
{
printf("swap, pMax[%d]:%d, pMin[%d]:%d\n", x, pMax[x], y, pMin[y]);
diff -= maxdiff;
swap(pMax + x, pMin + y);
print(A, n1);
print(B, n2);
printf("diff = %d\n", diff); }
else //没有找到可以交换的数字对,终止while循环
{
break;
}
}
return diff; //返回两个数组经交换后的最小差值
} int main(int argc, char **argv)
{ srand(time(NULL));
printf("min difference:%d\n", solve(, ));
// system("pause");
// pause();
return ;
}

import java.util.Arrays; /**
*
* @author Administrator
*
*/
public class TestUtil {
private int[] arrysMin = null; private int[] arrysMax = null; private int matchNum = 0; private boolean hasMatched = false; /**
* 返回数组的所有元素的总和
*
* @param arrays
* 待计算数组
* @return 所有元素的总和值
*/
public int getArraySum(int[] arrays) {
int sum = 0;
if (null != arrays) {
for (int i : arrays) {
sum += i;
}
}
return sum;
} /**
* 返回数组的差值
*
* @param array1
* 集合一
* @param array2
* 集合二
* @return 差值
*/
public int getTowArraysMacth(int[] array1, int[] array2) {
Integer l1 = getArraySum(array1);
Integer l2 = getArraySum(array2); if ((l1 - l2) / 2 > 0) {
arrysMax = array1;
arrysMin = array2;
return (l1 - l2) / 2;
} else {
arrysMax = array2;
arrysMin = array1;
return (l2 - l1) / 2;
}
} private boolean isReturn(int[] arrayMax, int[] arrayMin) {
Integer l1 = getArraySum(arrayMax);
Integer l2 = getArraySum(arrayMin); if ((l1 - l2) > 0) {
return false;
} else {
return true;
}
} public void doMatch() {
// 保证大的数组总和永远是大的，以防递归进入死循环
if (isReturn(arrysMax, arrysMin)) {
return;
}
// 获取元素总和大的与小的差值平均值
int diff = getTowArraysMacth(arrysMax, arrysMin);
// 使用一个大数字初始化最小绝对值，后面做比较
int abs = getArraySum(arrysMax);
int tempElement = 0;
// 最终大数组要交换的下标
int maxIndex = -1;
int minIndex = -1;
if (null != arrysMax && null != arrysMin) {
for (int i = 0; i < arrysMax.length; i++) {
for (int j = 0; j < arrysMin.length; j++) {
int temp = arrysMax[i] - arrysMin[j];
if (temp > 0 && diff > temp) {
// 如果元素差值和元素总和大的与小的差值平均值正好相等，直接交换元素OK
if (Math.abs(diff - temp) == 0) {
tempElement = arrysMin[j];
arrysMin[j] = arrysMax[i];
arrysMax[i] = tempElement;
matchNum++;
hasMatched = true;
return;
} else {
// 否则完全遍历，最终找出元素差值和总和差值平均值差距最小的两元素，
if (abs > Math.abs(diff - temp)) {
abs = Math.abs(diff - temp);
maxIndex = i;
minIndex = j;
}
}
}
}
}
//如果没有找到匹配项，且在已变换的数组中找到了满足条件的变量，则继续递归
if (!hasMatched && (maxIndex != -1 || minIndex != -1)) {
// 交换差距最小的两元素
System.out.printf("第%d次交换， Max[%d]:%d, Min[%d]:%d\n", ++matchNum, maxIndex, arrysMax[maxIndex], minIndex, arrysMin[minIndex]);
tempElement = arrysMin[minIndex];
arrysMin[minIndex] = arrysMax[maxIndex];
arrysMax[maxIndex] = tempElement;
System.out.println("交换后Max数组:" + Arrays.toString(arrysMax));
System.out.println("交换后Min数组:" + Arrays.toString(arrysMin));
System.out.println();
// 递归
doMatch();
}
}
} public int getMatchNum() {
return matchNum;
} /**
* @param args
*/
public static void main(String[] args) {
TestUtil tu = new TestUtil();
int[] a1 = { 11, 2, 4, 6, 47 };
int[] a2 = { 4, 5, 8, 9, 2 };
System.out.println("交换前数组a1：" + Arrays.toString(a1));
System.out.println("交换前数组a2：" + Arrays.toString(a2));
// 进行第一次分出，两元素的总和谁大谁小
tu.getTowArraysMacth(a1, a2);
// 开始进行处理交换
tu.doMatch();
// 打印交换结果
System.out.println("交换次数：" + tu.getMatchNum());
System.out.println("a1数组元素和:" + tu.getArraySum(a1));
System.out.println("a2数组元素和:" + tu.getArraySum(a2));
System.out.println("交换后原数组a1:" + Arrays.toString(a1));
System.out.println("交换后原数组a2:" + Arrays.toString(a2));
}
}