2.18 数组分割

1,题意:2n个正整数,分成两组n,使其和最接近.

2,思路:
动态规划: isOK[i][v]表示是否可以找打i个数,使得他们之和等于v.

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int m = 0xffff;
bool isOK[100][m];

void HalfSum(int data[], int N)
{
    memset(isOK, 0, sizeof(isOK));
    isOK[0][0] = true;
    int sum = 0;
    int n = N/2;
    for (int i = 0; i < N; ++i)
        sum += data[i];
    for (int k = 1; k < N; ++k)
    {
        for (int i = 1; i <= min(k, n); ++i)
        {
            for (int v = 1; v <= (sum / 2); ++v)
                if ((v >= data[k]) && isOK[i - 1][v - data[k]])
                    isOK[i][v] = true;
        }
    }
    int ret = sum / 2;
    while (!isOK[n][ret])
        --ret;
    cout << ret << endl;
}

int main()
{
    int data[] = {1, 5, 7, 8, 9, 6, 3, 11, 20, 17};
    HalfSum(data, sizeof(data) / sizeof(data[0]));
    return 0;
}