# coreBugZJ

## 0-1背包问题——算法作业 3.2，EOJ 1052

0-1背包问题

Time Limit:1000MS Memory Limit:30000KB
Total Submit:796 Accepted:276

Description

Input

Output

Sample Input

1
5 10
2 6
2 3
6 5
5 4
4 6

Sample Output

15

Source

ECNU算法作业

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, 0sizeof(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

posted on 2011-04-18 16:08 coreBugZJ 阅读(258) 评论(0)  编辑 收藏 引用 所属分类: 课内作业