D98jc. 集合划分
时间限制:1.0s 内存限制:256.0MB 代码提交间隔:3分钟(现在可以提交)
输入文件名:sets.in 输出文件名:sets.out
问题描述
给定n个整数,请将这n个整数分为两部分(个数不一定要等),使得第一部分的和大于且尽量接近第二部分的和的两倍。
输入格式
从文件sets.in中读入数据。
输入的第一行包含一个整数n。
第二行包含n个整数,表示给定的数。
输出格式
输出到文件sets.out中。
你不需要输出具体的划分方案,只要输出第一部分的和减去第二部分的和的两倍的值。
样例输入
4
3 8 7 4
样例输出
1
样例说明
3, 8, 4为一部分,7为另一部分,(3+8+4)–2×7=1。
数据规模和约定
对于40%的数据,1 ≤ n ≤ 20,给定的每个数为不超过100的正整数。
对于100%的数据,1 ≤ n ≤ 100,给定的每个数为不超过1000的正整数。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 33010;
int n;
int a[N];
int f[M];
int main()
{
int sum = 0;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
sum += a[i];
}
int v = (sum + 1) / 2;
memset(f, -0x3f, sizeof f);
f[0] = 0;
for(int i = 0; i < n; i++)
for(int j = v; j >= a[i]; j--)
f[j] = max(f[j], f[j - a[i]] + a[i]);
int res = abs(sum - 2 * f[v]);
cout << res << endl;
return 0;
}
0分,帮帮我