描述
题解
被包装后的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;
}