HHUOJ 1017 最小差（01背包）

1017: 最小差

时间限制: 1 Sec 内存限制: 128 MB
提交: 20 解决: 5
</center>

题目描述

假设有n个正整数a₁,a₂,a₃…a_n，希望将这些数分成两组，使得两组的和差值最小。

输入

第一行输入整数m(0<m<=100)，代表测试用例的数量。

接下来每个用例由两行组成，第一行是一个整数n（1<n<=100），表示整数的个数，第二行包含n个正整数，且最大不超过100。

输出

输出最小的差的绝对值。

样例输入

263 2 3 4 2 951 1 1 1 10

样例输出

提示

来源

河海ACM前辈-裴正

思路：

题意很清楚，n个数，分两组，两组的差最接近0。很自然的想到这是在类似于取东西，看怎么取得平均（就是说要使两组数都尽可能的接近sum/2）。所以只需要对一组进行求算使它最接近sum/2，那样的话另一组自然也是最接近的。这就是典型的01背包问题了，sum/2的体积求最多可以装多少。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int v[100+2];
int dp[100+2][100+2];

int main()
{
	//freopen("in.txt","r",stdin);
	int m;
	cin>>m;
	while(m--)
	{
		int n;
		scanf("%d",&n);
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&v[i]);
			sum+=v[i];
		}
	    int summ=sum/2;
		memset(dp,0,sizeof(dp));    
        dp[0][0]=0;    
        for(int i=1;i<=n;i++)    
            for(int j=summ;j>=0;j--)    
           {  
            if(j>=v[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+v[i]);  
            else dp[i][j]=dp[i-1][j];  
           }     
        printf("%d\n",abs(sum-2*dp[n][summ]));    
	}
}