标准的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 |
/** =====================================================================================** Filename: noippujizhuangxiang.c** Description: RT** Version: 1.0* Created: 2014-05-19 15:44:57* Revision: none* Compiler: gcc** Author: Rainboy (mn), 597872644@qq.com* Company: NONE** =====================================================================================*/#include <stdio.h>int
a[20001]={0};int
V,numofwupin=0;int
b[30]={0};int
main(int
argc, const
char *argv[]){scanf("%d",&V);scanf("%d",&numofwupin);int
i,j,k,l;for
(i = 0; i < numofwupin; i++) {scanf("%d",&b[i]);}for
(j = 0; j < numofwupin; j++) {for
(i = V; i >0; i--) {if((b[j]<=i) &&(b[j]+a[i-b[j]] > a[i]))a[i]= b[j] + a[i-b[j]];}}printf("%d\n",V-a[V]);return
0;} |
NOIP2001 普及组 装箱问题,布布扣,bubuko.com
原文：http://www.cnblogs.com/rainboy/p/3737064.html