51Nod 1007 正整数分组

将一堆正整数分为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

思路：

我们用sum表示数组和，我们要分成两个数组并使两个数组的和相差最小，那么我们应该尽量使和接近sum/2。这样就转化成了一个01背包了，在最大为sum/2的背包中可以放下的重量。

//Asimple
#include <bits/stdc++.h>
//#define INF 0x3fffffff
#define mod 1000000
#define swap(a,b,t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug(a)  cout << #a << " = "  << a <<endl
#define test() cout<<"=========="<<endl
using namespace std;
typedef long long ll;
const int maxn = 10000+5;
const double PI=acos(-1.0);
const int INF = ( 1 << 20 ) ;
const int dx[] = {-1, 0, 1, 0};  
const int dy[] = { 0,-1, 0, 1}; 
ll n, m, res, ans, len, T, k, num, sum;
int dp[maxn], a[maxn];

void input() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    sum = 0;
    for(int i=0; i<n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    CLS(dp, 0);
    for(int i=0; i<n; i++) {
        for(int j=sum/2; j>=a[i]; j--) {
            dp[j] = max(dp[j], dp[j-a[i]]+a[i]);
        }
    }
    cout << abs(sum-dp[sum/2]-dp[sum/2]) << endl;
}

int main(){
    input();
    return 0;
}