51Nod 1007：正整数分组（01背包）

1007 正整数分组 

基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题

将一堆正整数分为2组，要求2组的和相差最小。

例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。

Input

第1行：一个数N，N为正整数的数量。

第2 - N+1行，N个正整数。

(N <= 100, 所有正整数的和 <= 10000)

Output

输出这个最小差

Input示例

5

1

2

3

4

5

Output示例

1

思路

一开始看到这题感觉是贪心，但是又觉得好麻烦，完全没思路，不知道怎么贪，百度找了一下，发现竟然是背！包！！

仔细想一下也很好理解，可以看做是n个数字放在两个袋子里，所以对于每个数字，肯定会放在这两个袋子中的其中一个，即对于一个袋子来说，数字非0即1（1代表放进去，0代表不放）。因为题目要求的是求两个袋子里的最小差值，所以把袋子的容量设为这些数字总和的1/2 。去计算在这个袋子里最多能装下的价值是多少（把每个数字看做价值和体积均为本身数值的物品），因为最后要求的是差值，所以要用总价值减去装进一个袋子中的价值*2

AC代码

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#define ll long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x3f3f3f3f

const double E=exp(1);

const int maxn=1e6+10;

using namespace std;

int a[maxn];

int dp[maxn];

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	int n;

	cin>>n;

	int res=0;

	for(int i=0;i<n;i++)

	{

		cin>>a[i];

		res+=a[i];

	}

	for(int i=0;i<n;i++)

		for(int j=res/2;j>=a[i];j--)

			dp[j]=max(dp[j],dp[j-a[i]]+a[i]);

	int _=abs(res-2*dp[res/2]);

	cout<<_<<endl;

	return 0;

}