0-1背包問題
Time Limit:1000MS
Memory Limit:30000KB
Total Submit:796
Accepted:276
Description
已知n個(gè)物體{1,2,3....n}與一個(gè)背包。物體i的重量為Wi > 0，價(jià)值為Pi > 0 (i=1,2,...n)，背包容量為M > 0。
求在不超過背包容量的情況下，使得裝進(jìn)去的物體的價(jià)值最高。
Input
第一行為一個(gè)正整數(shù)N，表示有幾組測(cè)試數(shù)據(jù)。
每組測(cè)試數(shù)據(jù)的第一行為兩個(gè)整數(shù)n和M，0<n<=20,0<M<100000.
再下去的n行每行有兩個(gè)整數(shù)Wi和Pi, 0<Wi,Pi<10000.
Output
對(duì)于每組測(cè)試數(shù)據(jù)，輸出一行，只含一個(gè)整數(shù)，表示裝進(jìn)去物體的價(jià)值最高值。
Sample Input
1
5 10
2 6
2 3
6 5
5 4
4 6
Sample Output
15
Source
ECNU算法作業(yè)
空間優(yōu)化至 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