经典C面试题 -- 序列均衡

题目

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

交换后
a=[100, 40, 5, 4, 3, 3]
b=[99, 98, 2,2, 1, 1]

分析

1. 网上有思路采用 贪婪算法
大意为：
当前数组a与数组b的各自累加和的差为
    A = sum(a) - sum(b)
假设数组a的i元素与数组b的j元素互换，新的a数组与b数组各自累加和的差为
    A' = sum(a) + b[j] - a[i] - ( sum(b) + a[i] - b[j])
       = sum(a) - sum(b) - 2*(a[i] - b[j])
       = A - 2* (a[i] - b[j])

假设A大于0， 那么如果能够找到这样的a[i] 与b[j], 使得 |a[i] - b[j]| 在（0，A）之间，那么交换这两个元素，数组a与数组b累加和之间的差值将变小。

据此可以得出算法
    （1）计算数组a与数组b累加和差值，记为A；
    （2）在数组a与b之间选择这样一组元素，它们的差值比A小；
    （3）交换这组元素；
    （4）重复（1），（2），（3）步，直到找不到合适的元素组即完成。

网上有类似的算法，本文就不贴代码了。

上面的算法是一个典型的贪心算法，能够得到局部最优解，但未必能够得到全局最优。http://blog.csdn.net/cwqbuptcwqbupt/article/details/7521733， 对此作了反例。


2. 重新分析：
题目的一个等价命题为，给定2N个元素，累加和为SUM，从中选择N个元素，使得选择的N个元素的累加和尽量接近SUM/2 。

经过这样命题转换，我们把两个数组统筹在一起了，更有全局观了（废话）。这样从一堆物品中选择出一堆且满足一定要求，首先联想到背包问题。那么能不能转换为背包问题求解呢？

考虑
我们有一个背包容量为SUM/2的背包，给定物品有2N个，第i个物品的重量为w[i]，要求装入物品的个数恰好为N，且总重量尽量接近SUM/2。
上面定义转换为了一个背包问题，但又与常见的01背包问题有差别。事实上，该背包有两个限制：其一是物品个数，其二是物品总重量。

那么我们为每个元素定义两个属性：其一，重量属性，其二，数量属性（或体积属性）。

那么我们的“物品”和“背包”：
有2N个物品，第i个物品体积为c[i] (均为1）, 重量为w[i]。现有一个背包， 背包体积容量为N， 承重为W。如何选择物品装入背包中，使得背包恰好装满（体积），物品总重量不超过背包承重，且总重量达到最大？

由于物品重量既是限制又是目标，稍微有点混乱，我们再引入一个物品属性：价值（不过，凑巧的是物品价值和物品质量是相等的）。再定义如下：
有2N个物品，物品i 的体积为c[i]  (均为1）， 重量为 w[i], 价值为v[i]  (v[i] = w[i])。现有一个背包，背包体积容量为N，承重W。如何选择物品装入背包中，使得背包恰好装满（体积），物品总重量不超过背包承重，且价值最大？

至此，该问题已经转为一个标准的二维背包问题！

关于二维背包问题的求解方法本文就不详细阐述了，网上很容易找到。
附上采用二维背包问题求解过程的部分代码

int seriesBalance(int *list1, int* list2, int len)
{
    int sum = 0;

    int* wights;
    int* caps;
    int* vlues;

    array_t* arrayCur;
    array_t* arrayBk;

    array_t* pCur;
    array_t* pBk;
    array_t* pTemp;


    int pckgW;
    int pckgC;

    int col;
    int row;

    int val;
    int i, j, k;

    int drow;
    int dcol;

    wights = (int*) calloc(2 * len, sizeof(int));
    caps = (int*) calloc(2 * len, sizeof(int));
    vlues = (int*) calloc(2 * len, sizeof(int));
    //TO-DO: do alloc success check here


    for (i = 0; i < len; i++)
    {
        sum += (list1[i] + list2[i]);

        wights[i] = list1[i];
        wights[len + i] = list2[i];

        caps[i] = 1;
        caps[len + i] = 1;

        vlues[i] = list1[i];
        vlues[len + i] = list2[i];
    }

    pckgW = sum / 2; // 注意这里@pckgW跟数据内容有关，非常容易引发不稳定问题
    pckgC = len;

    arrayCur = newArray((pckgC+1) , (pckgW+1));
    arrayBk = newArray((pckgC+1) , (pckgW+1));
    //do malloc success check


    pCur = arrayCur;
    pBk = arrayBk;

    /*
    __0_1_2_3_4_5_6_7_8___w_
    0|0 0 0 0 0 0 0 0 0
    1|X X X X X X X X X
    2|X X X X X X X X X
    3|X X X X X X X X X

    c|

    fcwv(0,0,x)
    */
    for (row = 0; row <= pckgC; row++)
    {
        for (col = 0; col <= pckgW; col++)
        {
            if (row == 0)
            {
                setArray(pBk, row, col, 0);
            }
            else
            {
                setArray(pBk, row, col, (-2 * sum)); // 由于是恰好装满，那些不能满足恰好装满的选择方式都为负数
            }
        }
    }


    for (i = 0; i < 2 * len; i++)
    {
        for(row = 1; row <= pckgC; row++)
        {
            for(col = 1; col <= pckgW; col++)
            {
                if (row < caps[i] || col < wights[i])
                    val = getArray(pBk, row, col ); // 不装入，当前值是上一轮对于的值
                else
                    val = MAX( (getArray(pBk, row - caps[i], col - wights[i]) + vlues[i]), getArray(pBk, row, col));

                setArray(pCur, row, col, val);
            }
        }

        // 交换指针
        pTemp = pBk;
        pBk = pCur;
        pCur = pTemp;
    }


    val = -2*sum;
    for(row = pckgC; row > 0; row--)
    {
        for (col = pckgW; col > 0; col--)
            val = MAX(getArray(pBk, row, col), val);
    }

    free(arrayCur);
    free(arrayBk);
    free(wights);
    free(vlues);
    free(caps);

    return val;
}

上述函数实现功能输入两个数组，返回它们均衡后，较小数组的累加和。其中部分函数的实现未全部给出（比较简单）。

至此，本题的思路已经比较明确了。但上面的代码并未完整解决题目的要求，需要稍加改进。这个就不深入讨论了。
另外，值得一提的是，实现中采用了根据数据内容来分配内存的方式，在实际使用中会存在很大的安全或性能隐患（比如，数据差距很大，会导致分配巨额内存）。