分西瓜（dfs）

描述

今年暑假计算机学院带领大二的计算机专业学生实习，在实习过程中计科一班和计科二班表现突出，辅导员决定买一堆西瓜奖励这两个班，为了对每个班公平，她想让两堆的重量之差最小。每个西瓜的重量已知，你能帮帮她么？

输入:

第一行输入西瓜数量N (1 ≤ N ≤ 20)

第二行有N个数，W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量

输出:

输出分成两堆后的最小质量差

样例输入:

5 8 13 27 14

样例输出:

 1 //深度优先搜索
 2 #include <iostream>
 3 #include <string.h>
 4 #include <cmath>
 5 using namespace std;
 6 int allmax=0,a[100];
 7 int allsum=0;
 8 void dfs(int sum,int i)
 9 {
10     if(i<0)
11         return ;
12     int max;
13     if(allsum>2*sum)
14         max=allsum-2*sum;
15     else
16         max=2*sum-allsum;
17     if(allmax>max)
18         allmax=max;
19     dfs(sum+a[i],i-1);
20     dfs(sum,i-1);
21 }
22 int main()
23 {
24     int n;
25     while(cin>>n)
26     {
27         int i;
28         memset(a,0,sizeof(a));
29         allmax=9999999;
30         for(i=0; i<n; i++)
31         {
32             cin>>a[i];
33             allsum=allsum+a[i];
34         }
35         dfs(0,n-1);
36         cout<<allmax<<endl;
37         allsum=0;
38     }
39     return 0;
40 }