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>