[51NOD1007] 正整数分组（DP，记忆化搜索）

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1007

dp(id, s)表示第id个数之前，其中一个集合和为s的差，按照取和不取dfs就行。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 110;
 5 const int maxm = 11000;
 6 const int inf = 100100100;
 7 int n;
 8 int a[maxn], sum;
 9 int dp[maxn][maxm];
10 
11 int dfs(int id, int s) {
12   if(id == n+1) return abs(s-(sum-s));
13   if(~dp[id][s]) return dp[id][s];
14   return dp[id][s] = min(dfs(id+1, s), dfs(id+1, s+a[id]));
15 }
16 
17 int main() {
18   // freopen("in", "r", stdin);
19   while(~scanf("%d", &n)) {
20     memset(dp, -1, sizeof(dp));
21     sum = 0;
22     for(int i = 1; i <= n; i++) {
23       scanf("%d", &a[i]);
24       sum += a[i];
25     }
26     printf("%d
", dfs(1, 0));
27   }
28   return 0;
29 }