Posted on 2009-03-12 20:51
Hero 閱讀(520)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //Accepted 62 9512 865 C++
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
6
7 const int size = 1200 ;
8 int w[size] ;
9 int v[size] ;
10 int dp[size][2010] ;
11 int DP[2010] ;
12
13 int inn, inc ;
14
15 int fmax( int a, int b )
16 {
17 return a > b ? a : b ;
18 }
19
20 int main1()
21 {
22 while( scanf( "%d %d", &inn, &inc ) != EOF )
23 {
24 for( int i=1; i<=inn; i++ ) scanf( "%d", &w[i] ) ;
25 for( int i=1; i<=inn; i++ ) scanf( "%d", &v[i] ) ;
26
27 memset( dp, 0, sizeof(dp) ) ;
28
29 for( int j=0; j<=inc; j++ )
30 {
31 if( j >= w[1] ) dp[1][j] = v[1] ;
32 }
33 for( int i=2; i<=inn; i++ )
34 {
35 for( int j=0; j<=inc; j++ )
36 {
37 //dp[i][j] = fmax( dp[i-1][j], dp[i-1][j-w[i]]+v[i] ) ;
38 if( j - w[i] >= 0 )
39 {
40 dp[i][j] = fmax( dp[i-1][j], dp[i-1][j-w[i]]+v[i] ) ;
41 }
42 else
43 {
44 dp[i][j] = dp[i-1][j] ;
45 }
46 }
47 }
48
49 printf( "%d\n", dp[inn][inc] ) ;
50 }
51 return 0 ;
52 }
53 // 1006 Accepted 0 9520 1449 C++
54 int main()
55 {
56 while( scanf( "%d %d", &inn, &inc ) != EOF )
57 {
58 for( int i=1; i<=inn; i++ ) scanf( "%d", &w[i] ) ;
59 for( int i=1; i<=inn; i++ ) scanf( "%d", &v[i] ) ;
60
61 memset( DP, 0, sizeof(DP) ) ;
62
63 for( int j=0; j<=inc; j++ )
64 {
65 if( j >= w[1] ) DP[j] = v[1] ;
66 }
67 for( int i=2; i<=inn; i++ )
68 {
69 for( int j=inc; j>=0; j-- )
70 {
71 if( j - w[i] >= 0 )
72 DP[j] = fmax( DP[j], DP[j-w[i]]+v[i] ) ;
73 else
74 DP[j] = DP[j] ;
75 }
76 }
77
78 printf( "%d\n", DP[inc] ) ;
79 }
80
81 return 0 ;
82 }