装箱问题
Time Limit:1000MS
Memory Limit:30000KB
Total Submit:660
Accepted:296
Description
有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0<n≤30），每个物品有一个体积（正整数）。要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
Input
输入有多组测试数据，第一行一个正整数V,表示箱子的容量
第二行一个数据n表示物品个数。
第三行有n个数据，描述每个物品的体积
Output
每个输出占一行，输出箱子最后剩下的最小体积
Sample Input
24 一个整数，表示箱子容量
6 一个整数，表示有n个物品
8 3 12 7 9 7分别表示这n个物品的各自体积
Sample Output
0 一个整数，表示箱子剩余空间
hint:汉字是不需要处理的，只是为了描述题目
你也可以考虑其他的方法。
Source
ECNU算法作业
0-1 背包：
1 #include <iostream>
2 #include <cstring>
3
4 using namespace std;
5
6 const int L = 20003;
7 bool have[ L ];
8
9 int main(){
10 int v, n, w, j;
11 while( cin >> v ){
12 memset( have, 0, sizeof(have) );
13 have[ 0 ] = true;
14 cin >> n;
15 while( n-- ){
16 cin >> w;
17 for( j = v; j >= w; --j ){
18 have[ j ] = have[ j ] || have[ j - w ];
19 }
20 }
21 for( j = v; ! have[ j ]; --j )
22 ;
23 cout << v - j << endl;
24 }
25 return 0;
26 }
27