NOIP2001 普及组 装箱问题

标准的01背包，就不写分析了，标准就看 我的背包问题的解析

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

35

36

37

38

39

40

41

42

43

44

<code>/*</code>

<code>* =====================================================================================</code>

<code>*</code>

<code>* Filename: noippujizhuangxiang.c</code>

<code>* Description: RT</code>

<code>* Version: 1.0</code>

<code>* Created: 2014-05-19 15:44:57</code>

<code>* Revision: none</code>

<code>* Compiler: gcc</code>

<code>* Author: Rainboy (mn), [email protected]</code>

<code>* Company: NONE</code>

<code>*/</code>

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

<code>int</code>

<code>a[20001]={0};</code>

<code>V,numofwupin=0;</code>

<code>b[30]={0};</code>

<code>main(</code><code>int</code>

<code>argc,</code><code>const</code>

<code>char</code> <code>*argv[])</code>

<code>{</code>

<code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;V);</code>

<code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;numofwupin);</code>

<code>i,j,k,l;</code>

<code>for</code>

<code>(i = 0; i &lt; numofwupin; i++) {</code>

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

<code>}</code>

<code>(j = 0; j &lt; numofwupin; j++) {</code>

<code>(i = V; i &gt;0; i--) {</code>

<code>if</code><code>((b[j]&lt;=i) &amp;&amp;(b[j]+a[i-b[j]] &gt; a[i]))</code>

<code>a[i]= b[j] + a[i-b[j]];</code>

<code>printf</code><code>(</code><code>"%d\n"</code><code>,V-a[V]);</code>

<code>return</code>

<code>0;</code>