51Nod－1007－正整数分组

ACM模版

描述

题解

被包装后的01背包。所有整数和最大为10000，所以只要求在sum/2的背包中，最大的价值，然后fabs(sum - dp[N][C] - dp[N][C])即为结果。

代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN = 110;
const int MAXM = 5e3 + 10;

int A[MAXN];
int dp[MAXM][MAXM];

int main(int argc, const char * argv[])
{
// freopen("input.txt", "r", stdin);

    int N;
    cin >> N;

    int sum = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> A[i];
        sum += A[i];
    }
    int C = sum / 2;
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= C; j++)
        {
            if (j < A[i])
            {
                dp[i][j] = dp[i - 1][j];
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - A[i]] + A[i]);
            }
        }
    }
// cout << dp[N][C] << '\n';
    cout << fabs(sum - dp[N][C] - dp[N][C]) << '\n';

    return 0;
}