Posted on 2009-06-25 15:27
Hero 阅读(161)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
1 //HLOJ 1038 Accepted 15 356 1018 C++
2
3 //动态规划
4
5 #include <iostream>
6 #include <string>
7 #include <algorithm>
8 using namespace std ;
9
10 const int size = 200 ;
11
12 int w[size] ;
13 int v[size] ;
14 int dp[size][size] ;
15
16 int tnum ;
17 int inn, inm, ins ;
18
19 int fmax( int a, int b )
20 {
21 return a > b ? a : b ;
22 }
23
24 int main()
25 {
26 while( cin>>inn>>inm>>ins )
27 {
28 for( int i=1; i<=ins; i++ )
29 {
30 cin >> v[i] >> w[i] ;
31 }
32
33 memset( dp, 0, sizeof(dp) ) ;
34
35 for( int j=0; j<=inm; j++ )
36 {
37 if( j - w[1] >= 0 )
38 dp[1][j] = v[1] ;
39 else
40 dp[1][j] = 0 ;
41 }
42
43 for( int i=2; i<=ins; i++ )
44 {
45 for( int j=0; j<=inm; j++ )
46 {
47 if( j-w[i] >= 0 )
48 {
49 dp[i][j] = fmax( dp[i-1][j], dp[i-1][j-w[i]]+v[i] ) ;
50 }
51 else
52
53 {
54 dp[i][j] = dp[i-1][j] ;
55 }
56 }
57 }
58
59 int minout = -1 ;
60 for( int j=0; j<=inm; j++ )
61 {
62 if( dp[ins][j] >= inn )
63 {
64 minout = j ; break ;
65 }
66 }
67
68 if( minout < 0 )
69 printf( "%d\n", minout ) ;
70 else
71 printf( "%d\n", inm - minout ) ;
72 }
73 return 0 ;
74 }