数组分割问题

　　昨天同学问我一道关于数组分割的问题——有一个无序、元素个数为2n的正整数数组，要求：如何能把这个数组分割为元素个数为n的两个数组，并是两个子数组的和最接近。

　　假设2n个整数之和为sum。从2n个整数中找出n个元素的和，有三种可能：大于sum/2,等于sum/2，小于sum/2。可以考虑小于等于sum/2的情况。使用动态规划解决这个问题，其实这是一个NP问题，只能尽量去接近sum/2这个值。

　　我们可以定义dp[k][s]代表从前k个数中去任意个元素，且k小于等于n，其和为s是否存在；之所以将选出的数之和放在下标中，而不是作为dp[k]的值，是因为那种做法不满足动态规划的前提——最优化原理。

　　

#include <iostream>
#include <mem.h>
using namespace std;
const int MaxN = 100;
const int maxSum = 100000;
bool dp[MaxN][maxSum];
int A[MaxN];
int main()
{
    int n, k, i, s;
    cin >> n;
    for(i = 1; i <= 2*n; i++)
    {
        cin >> A[i];
    }
    int sum = 0;
    for(i = 1; i <= 2*n; i++)
        sum += A[i];
    memset(dp, false, sizeof(dp));
    dp[0][0] = true;
    for(k = 1; k <= 2*n; k++)
    {
        for(i = min(k, n);i >= 1; i--)
        {
            for(s = 1; s <= sum/2; s++)
            {
                if(s >= A[k] && dp[i-1][s-A[k]])
                    dp[i][s] = true;
            }
        }
    }
    for(s = sum/2; s >= 1 && !dp[n][s]; s--);
    cout << "s1 = " << s << ";" << "s2 = " << sum - s << endl;
    return 0;
}