假设所有西瓜重 Asum，所求的是用 Asum / 2 的背包装，最多装下多少。
刚开始用贪心作的，WA。后来用01背包，结果TLE，数据太大。原来用的是深搜！
dfs(int sum, int i) 表示当前装已了 sum，对第 i 个进行决策。
用时1200多MS，不知道大牛们60MS是怎么搞的，泥煤，20倍！以后再优化吧。
代码如下：
#include<iostream>
#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
int a[], Asum, mi;
void dfs(int sum, int i)
{
if(i < ) //西瓜已经试装完，返回
return;
int t = fabs(Asum - * sum); //两兄弟所分西瓜重量之差
if(t < mi)
mi = t;
if( * sum - Asum >= mi) //剪枝，重量之差已大于或等于已求最小值，往后再搜还是大于或等于
return;
dfs(sum + a[i], i - ); //装第 i 个
dfs(sum, i - ); //不装第 i 个
}
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
Asum = ;
mi = ;
for(int i = ; i < n; i ++)
{
scanf("%d", &a[i]);
Asum += a[i];
}
dfs(, n - ); //从什么都不装，对最后一个西瓜决策开始
cout <<mi <<endl;
}
return ;
}