动态规划（5）——01背包问题（NYOJ325zb的生日）

时间限制：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></dd>

多组测试数据（&lt;=1500）。数据以EOF结尾

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

第二行有N个数，W1, …, Wn (1 ≤ Wi ≤

10000)分别代表每个西瓜的重量

<dt>输出</dt>

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

<dt>样例输入</dt>

<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

32

33

34

<code>#include&lt;iostream&gt;</code>

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

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

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

<code>#include&lt;algorithm&gt;</code>

<code>using</code>

<code>namespace</code> <code>std;</code>

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

<code>int</code>

<code>zhiliang[21];</code>

<code>dp[100001]={0};</code>

<code>main()</code>

<code>{</code>

<code>    </code><code>int</code>

<code>n;</code><code>long</code>

<code>long</code> <code>v,sum;</code>

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

<code>    </code><code>{</code>

<code>        </code><code>sum=0;</code>

<code>        </code><code>for</code><code>(</code><code>int</code>

<code>i=0;i&lt;n;i++)</code>

<code>        </code><code>{</code>

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

<code>            </code><code>sum+=zhiliang[i];       </code>

<code>        </code><code>}</code>

<code>        </code><code>v=sum/2;</code>

<code>        </code><code>fill(dp,dp+v+1,0);</code>

<code>            </code><code>for</code><code>(</code><code>int</code>

<code>j=v;j&gt;=zhiliang[i];j--)</code>

<code>            </code><code>{</code>

<code>                    </code><code>dp[j]=Max(dp[j],dp[j-zhiliang[i]]+zhiliang[i]);       </code>

<code>            </code><code>}       </code>

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

<code>    </code><code>}</code>

<code>    </code><code>system</code><code>(</code><code>"pause"</code><code>);   </code>

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

<code>0;</code>

<code>}</code>

　　dfs的AC代码：

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

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

<code>V,ans,n,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>        </code><code>ans = max(ans,cnt);</code>

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

<code>;</code>

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

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

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

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

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

<code>        </code><code>ans = 0;</code>

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

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

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

<code>        </code><code>V = sum[n]/2;</code>

<code>        </code><code>dfs(n,0);</code>

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

<code>}       </code>