coreBugZJ

此 blog 已弃。

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

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, 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)  编辑 收藏 引用 所属分类: 课内作业


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理