0-1背包問題
Time Limit:1000MS
Memory Limit:30000KB
Total Submit:796
Accepted:276
Description
已知n個物體{1,2,3....n}與一個背包。物體i的重量為Wi > 0，價值為Pi > 0 (i=1,2,...n)，背包容量為M > 0。
求在不超過背包容量的情況下，使得裝進去的物體的價值最高。
Input
第一行為一個正整數N，表示有幾組測試數據。
每組測試數據的第一行為兩個整數n和M，0<n<=20,0<M<100000.
再下去的n行每行有兩個整數Wi和Pi, 0<Wi,Pi<10000.
Output
對于每組測試數據，輸出一行，只含一個整數，表示裝進去物體的價值最高值。
Sample Input
1
5 10
2 6
2 3
6 5
5 4
4 6
Sample Output
15
Source
ECNU算法作業
空間優化至 O ( m ) ：
1 #include <stdio.h>
2 #include <string.h>
3
4 #define M 100003
5
6 int f[M];
7
8 int main(){
9 int td, n, m, j, w, p;
10 scanf( "%d", &td );
11 while( td-- ){
12 scanf( "%d%d", &n, &m );
13 memset( f, 0, sizeof(f) );
14 while( n-- ){
15 scanf( "%d%d", &w, &p );
16 for( j = m; j >= w; --j ){
17 if( f[ j - w ] + p > f[ j ] ){
18 f[ j ] = f[ j - w ] + p;
19 }
20 }
21 }
22 printf( "%d\n", f[ m ] );
23 }
24 return 0;
25 }
26