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