一个数组由2n个整数组成，把这个数组分成两半，各有n个整数，求一个分法，使这两个子数组和的差最小

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

可以用动态规划来解决这个问题。代码如下：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_PEOPLE 100
#define MAX_WEIGHT 450
#define MAX_WEIGHT_SUM MAX_PEOPLE*MAX_WEIGHT
using namespace std;

int weights[MAX_PEOPLE];
//bool table[MAX_PEOPLE + 1][MAX_WEIGHT_SUM + 1]; 

bool** create2D(int x, int y) {
    bool **array = new bool*[x];
    for (int i = 0; i < x; ++i) {
        array[i] = new bool[y];
        memset(array[i], 0, sizeof(bool)*y);
    }
    return array;
}

void delete2D(int x, int y, bool **array) {
    for (int i = 0; i < x; ++i) {
        delete[] array[i];
    }
    delete[] array;
}

void memset2D(int x, int y, bool **array) {
    for(int i = 0; i < x; ++i)
        memset(array[i], 0, sizeof(bool)*y);
}

int main(void) {
    int n, N, W, maxDiff, teamWeight, temp;
    int minWeight = MAX_WEIGHT, maxWeight = -1;
    cin >> N;
    while(N--) {
        cin >> n;
        W = 0;
        for(int i = 0; i < n; ++i) {
            cin >> weights[i];
            if(weights[i] < minWeight)
                minWeight = weights[i];
            if(weights[i] > maxWeight)
                maxWeight = weights[i];

            W += weights[i];
        }
        int maxW = maxWeight + (W>>1);
        int maxn = n>>1;
        int index = 0;
    /* 
       table[j][i] = 1 if a team of j people can form i weight 
                        from K people, where k is implicit in loop
       table[j][i] = table[j-1][i-weight[j]] if i-weight[j] >=0
     */
        bool **table = create2D(maxn+1, maxW+1);
        //memset2D(maxn+1, maxW+1, table);
        //memset(table, 0, sizeof(table));
        table[0][0] = true;
        /* for k people what can be formed?*/
        for(int k = 0; k < n; ++k) {
            /* forming team of size j out of k people*/
            for(int j = min(k, maxn) ; j >= 1; --j) { 
                /* using j people out of k, can I make weight i?*/
                for(int i = maxW; i >=minWeight ; --i) {
                    if (table[j][i] == false) {
                        /*do not consider k if more than allowable*/
                        index = i - weights[k];
                        if (index < 0) break;
                        /*if without adding k, we can make the weight
                          limit with less than one person then one can
                          also make weight limit by adding k.*/
                        table[j][i] = table[j-1][index];
                    } /*outer if ends here*/
                } /* ith loop */
            } /* jth loop */
        } /* kth loop */

        maxDiff = MAX_WEIGHT_SUM ;
        teamWeight = 0;
        for(int i = 0; i <= maxW; ++i) {
            if (table[n/2][i]) {
                temp = abs(abs(W - i) - i);
                if (temp < maxDiff) {
                    maxDiff = temp;
                    teamWeight = i;
                }
            }
        }
        //delete2D(n+1, maxW+1, table);
        teamWeight = min(teamWeight, W-teamWeight);
            cout << teamWeight << " " << W - teamWeight << endl;
        if(N)
            cout << endl;
    }
        return 0;
}