【动态规划】数字分组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[1555555]={0},sum,n; int a[33]; int main() { cin>>n; sum=0; memset(f,0,sizeof(f)); for(int i=0;i<n;i++) { cin>>a[i]; sum+=a[i]; } for(int i=0;i<n;i++) { for(int j=sum/2;j>=a[i];j--) { f[j]=max(f[j],f[j-a[i]]+a[i]); } } cout<<sum-2*f[sum/2]<<endl; return 0; }