#include <stdio.h>  
#include <cmath>  
#include <algorithm>  
using namespace std;  

int a[21],total,n,m;
 
void DFS(in    t s,int i)  
{  
    if(i==n)
        return;  
    if(fabs(2*s-total)<m)   
        m = fabs(2*s-total);
   
    DFS(s+a[i],i+1);  
    DFS(s,i+1);              //为什么要用两次递归
    return;  
}  

int main()  
{  
    int i,j;  
    while(~scanf("%d",&n))  
    {  
        total = 0,m = 0x3f3f3f3f;  
        for(i = 0;i<n;i++)  
        {  
            scanf("%d",&a[i]);  
            total += a[i];  
        }  
        DFS(0,0);  
        printf("%d\n",m);  
    }  
    return 0;  
}

今天是阴历七月初五，acm队员zb的生日。zb正在和C小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日，经过调查，zb发现C小加和never都很喜欢吃西瓜，而且一吃就是一堆的那种，zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候，遇到了一个难题，never和C小加不在一块住，只能把西瓜分成两堆给他们，为了对每个人都公平，他想让两堆的重量之差最小。每个西瓜的重量已知，你能帮帮他么？
输入
多组测试数据（<=1500）。数据以EOF结尾
第一行输入西瓜数量N (1 ≤ N ≤ 20)
第二行有N个数，W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量
输出
输出分成两堆后的质量差

这个不就是典型的dp问题么~你这样用组合穷举也行~
调用两次就是穷举所有s和s+a[i]的所有可能~
我知道另一种解法可以参考n个数之和是否等于k这类的问题,具体解法类似于0 -1背包那样动规就可以了~
开一个数组记录数据然后查表在中间向两边寻找差值最小的就可以了~
2的20次方约摸为100万,西瓜总和最大据题意为20万,然后时间复杂度为20万乘以20个元素为400万,所以综合比较还是递归简单~

[此贴子已经被作者于2018-1-7 00:49编辑过]

谢谢。