Zb的生日

时间限制：3000 ms

 |  内存限制：65535 kb

难度：2

<dl></dl>

<dt>描述</dt>

<dd>今天是阴历七月初五，acm队员zb的生日。zb正在和c小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日，经过调查，zb发现c小加和never都很喜欢吃西瓜，而且一吃就是一堆的那种，zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给c小加和never的时候，遇到了一个难题，never和c小加不在一块住，只能把西瓜分成两堆给他们，为了对每个人都公平，他想让两堆的重量之差最小。每个西瓜的重量已知，你能帮帮他么？</dd>

<dt>输入</dt>

<dd>多组测试数据（&lt;=1500）。数据以eof结尾</dd>

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

第二行有n个数，w1, …, wn

(1 ≤ wi ≤ 10000)分别代表每个西瓜的重量

<dt>输出</dt>

<dd>输出分成两堆后的质量差</dd>

<dt>样例输入</dt>

<dd></dd>

<dt>样例输出</dt>

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

<code>#include&lt;stdio.h&gt;</code>

<code>#define max(a,b) a&gt;b?a:b</code>

<code>int</code>

<code>v,ans,n,i,w[21],sum[21];</code>

<code>void</code>

<code>dfs(</code><code>int</code>

<code>i,</code><code>int</code>

<code>cnt)</code>

<code>{</code>

<code>if</code><code>(i==0)</code>

<code>ans = max(ans,cnt);</code>

<code>return</code><code>;</code>

<code>}</code>

<code>if</code><code>(ans==v||cnt+sum[i]&lt;=ans)</code>

<code>return</code>

<code>;</code>

<code>if</code><code>(cnt+w[i]&lt;=v)</code>

<code>dfs(i-1,cnt+w[i]);</code>

<code>dfs(i-1,cnt);</code>

<code>main()</code>

<code>while</code><code>(~</code><code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;n))</code>

<code>ans=0;</code>

<code>for</code><code>( i=1;i&lt;=n;i++)</code>

<code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;w[i]);</code>

<code>sum[i]=sum[i-1]+w[i];</code>

<code>v=sum[n]/2;&lt;br&gt;dfs(n,0);</code>

<code>printf</code><code>(</code><code>"%d\n"</code><code>,sum[n]-ans*2);</code>

<code>0;</code>