Description：
拿到小金刚的宝藏是每个探险者的梦想。终于有两个寻宝者找到了小金刚的宝藏。里面包含着n个物品，每个物品的价值为w[i]，他们决定将财宝平均分。suma代表寻宝者A所获物品的总价值，sumb代表寻宝者B所获物品的总价值，请问怎么分配，能使得|suma - sumb|（即suma与sumb之差的绝对值）最小。
Input：
第一行输入一个T(T<20),代表每组有T个测试数据，接下来每组数据分两行，第一行是一个n(n<100)代表有n个财宝，接下来一行有n个数字，分别代表每个财宝的价值，价值<1000.
Output：
对于每一组数据，输出最小的|suma - sumb|（即suma与sumb之差的绝对值）.
Sample Input：
2
2
12 13
4
1 3 5 7
Sample Output：
1
0
拿到小金刚的宝藏是每个探险者的梦想。终于有两个寻宝者找到了小金刚的宝藏。里面包含着n个物品，每个物品的价值为w[i]，他们决定将财宝平均分。suma代表寻宝者A所获物品的总价值，sumb代表寻宝者B所获物品的总价值，请问怎么分配，能使得|suma - sumb|（即suma与sumb之差的绝对值）最小。
Input：
第一行输入一个T(T<20),代表每组有T个测试数据，接下来每组数据分两行，第一行是一个n(n<100)代表有n个财宝，接下来一行有n个数字，分别代表每个财宝的价值，价值<1000.
Output：
对于每一组数据，输出最小的|suma - sumb|（即suma与sumb之差的绝对值）.
Sample Input：
2
2
12 13
4
1 3 5 7
Sample Output：
1
0
题意：有两个寻宝者要瓜分小金刚的宝藏（宝藏其实就是一个长度为n的序列。。。），那么显然有时候宝藏分的是不平均的，那么问这两个人尽可能平均的分完宝藏后，两个人宝藏之间最小的差值是多少。
分析：我们可以先计算宝藏的价值总和sum，那么平均分的话就是每个人尽可能的得到的价值是sum/2，分析到这里就可以看出这其实是一道背包题，我们让背包的总容量为sum/2，有n件物品，显然每件物品都只有1件，只有放与不放的情况，由此这是一道裸的01背包题。
01背包：（01背包一般解决的问题是：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。）
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
详解：若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
但是这样算的空间复杂度比较高，我们还可以降低空间复杂度，用一维来算，先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v -c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..c[i]的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i -1][v-c[i]]的值（如果v=c[i]..V，那么当v增大时，f[v-c[i]就不是f[i-1][v-c[i]]的值了，而是f[i][v-c[i]]的值），那么新的递推公式就出来了：f[v]=max{f[v],f[v-c[i]]+w[i]};（以后都可以用一维来写啦，方便，简单，棒棒哒）。
显然这道题，只有一个变量，我们姑且当做只有物体的容量，那么就更简单了，下面贴上此题代码：
#include<stdio.h> #include<string.h> #include<queue> #include<math.h> #include<stdlib.h> #include<algorithm> using namespace std; const int N=1e6+10; const int INF=0x3f3f3f3f; const int MOD=2008; typedef long long LL; int a[110], dp[N]; int main () { int T, n, i, j, sum, suma, sumb, ans; scanf("%d", &T); while (T--) { sum = 0; scanf("%d", &n); for (i = 1; i <= n; i++) { scanf("%d", &a[i]); sum += a[i]; } memset(dp, 0, sizeof(dp)); for (i = 1; i <= n; i++) { for (j = sum/2; j >= a[i]; j--) { dp[j] = max(dp[j], dp[j-a[i]]+a[i]); } } suma = dp[sum/2]; sumb = sum-suma; ans = abs(suma-sumb); printf("%d ", ans); } return 0; }