动态规划-正整数分组

题源：51nod 1007

题意：输入一串数字，将他们分成两组，求两组之和差距最小的数字。

背包问题，将数字当做物品的重量，容量是总和的一半

代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <math.h>
#include <algorithm> 
using namespace std;
typedef long long ll;
const int maxn = 10100;
int dp[maxn],ss[maxn];
int s = 0,sum = 0;
int minn = 1e7;
int main()
{
    int t;
    cin >> t;
    for(int i = 1;i <= t;++i){
        cin >> dp[i];
        s += dp[i];
    }
    sum = s;
    s /= 2;
    memset(ss,0,sizeof(ss));
    for(int i = 1;i <= t;++i){
        for(int j = s;j >= dp[i];--j){
            ss[j] = max(ss[j],ss[j-dp[i]]+dp[i]); 
        }
    }
    cout << sum-2*ss[s] << endl;
    return 0;
 }