【动态规划】数字分组I
时间限制: 1 Sec 内存限制: 64 MB
提交: 10 解决: 6
[提交][状态][讨论版]
题目描述
给出一堆魔法石的重量，问如何分成两堆，使得它们质量和之差最小，求出这个最小值。
输入
第一行一个数n (n ≤30)。 接下来n行，每行一个正整数。(每个数≤100000)
输出
一个整数表示两组数字和的最小差。
样例输入
5
1 2 3 4 5
样例输出
1 将问题转化为求背包容量为所有数总和一半的背包问题
#include <iostream>
#include <cstring> using namespace std;
int f[]={},sum,n;
int a[];
int main()
{
cin>>n;
sum=;
memset(f,,sizeof(f));
for(int i=;i<n;i++)
{
cin>>a[i];
sum+=a[i];
}
for(int i=;i<n;i++)
{
for(int j=sum/;j>=a[i];j--)
{
f[j]=max(f[j],f[j-a[i]]+a[i]);
} }
cout<<sum-*f[sum/]<<endl;
return ;
}