首页 > 代码库 > 【编程题目】有两个序列 a,b,大小都为 n,序列元素的值任意整数,无序;(需要回头仔细研究)

【编程题目】有两个序列 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 = 0;    static int sumt = 0;    static int num = 0;    if(len < N)    {        return;    }    if(N == 0)    {        if(sumt <= sum/2 && sumt > sumtmax)        {            sumtmax = sumt;        }        printf("%d : %d  %d\n", ++num, sumt, sumtmax);        return;    }    choose(c, len - 1, N, sum);    sumt += c[len - 1];    choose(c, len - 1, N - 1, sum);    sumt -= c[len - 1];}void exchange(int * a, int * b, int len){    int * c = (int *)malloc(2 * len * sizeof(int));    int * smaller = (int *)malloc(len * sizeof(int));    int sum = 0;    for(int i = 0; i < len; i++)    {        c[i] = a[i];        sum += a[i];    }    for(int i = 0; i < len; i++)    {        c[i + len] = b[i];        sum += b[i];    }    choose(c, len * 2, 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 = 0;    for(; n; n &= n-1, result++);    return result;}void exchange2(int * a, int * b, int len){    int * c = (int *)malloc(2 * len * sizeof(int));    int * smaller = (int *)malloc(len * sizeof(int));    int sum = 0;    for(int i = 0; i < len; i++)    {        c[i] = a[i];        sum += a[i];    }    for(int i = 0; i < len; i++)    {        c[i + len] = b[i];        sum += b[i];    }    int maxsumh = 0;    int mask = 0;    for(int i = 0; i < (1 << len * 2); i++)    {        if(bit_c(i) == len)        {            int sumhalf = 0;            for(int j = 0; j < len * 2; j++)            {                if(((i >> j) & 1) == 1)                {                    sumhalf += c[j];                }            }            if(sumhalf <= sum / 2 && sumhalf > maxsumh)            {                maxsumh = sumhalf;                mask = i;            }        }    }    int ai = 0, bi = 0;    for(int j = 0; j < len * 2; j++)    {        if(((mask >> j) & 1) == 1)        {            a[ai++] = c[j];        }        else        {            b[bi++] = c[j];        }    }    printf("最小差值为:%d", sum - 2 * maxsumh);    free(c);    }int main(){    int a[5] = {1,2,3,4,5};    int b[5] = {30, 40, 50, 60, 23};    exchange2(a, b, 5);    return 0;}

 

网上有各种解法:

http://blog.csdn.net/tianshuai1111/article/details/7479767 中提出了两种。

但其中一种被http://blog.csdn.net/cwqbuptcwqbupt/article/details/7521733 用反例否决了。

http://blog.csdn.net/ljsspace/article/details/6434621# 中用到了回溯法 但评论中说存在问题 我还没仔细看