裝箱問(wèn)題
Time Limit:1000MS
Memory Limit:30000KB
Total Submit:660
Accepted:296
Description
有一個(gè)箱子容量為V（正整數(shù)，0≤V≤20000），同時(shí)有n個(gè)物品（0<n≤30），每個(gè)物品有一個(gè)體積（正整數(shù)）。要求從n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。
Input
輸入有多組測(cè)試數(shù)據(jù)，第一行一個(gè)正整數(shù)V,表示箱子的容量
第二行一個(gè)數(shù)據(jù)n表示物品個(gè)數(shù)。
第三行有n個(gè)數(shù)據(jù)，描述每個(gè)物品的體積
Output
每個(gè)輸出占一行，輸出箱子最后剩下的最小體積
Sample Input
24 一個(gè)整數(shù)，表示箱子容量
6 一個(gè)整數(shù)，表示有n個(gè)物品
8 3 12 7 9 7分別表示這n個(gè)物品的各自體積
Sample Output
0 一個(gè)整數(shù)，表示箱子剩余空間
hint:漢字是不需要處理的，只是為了描述題目
你也可以考慮其他的方法。
Source
ECNU算法作業(yè)
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