Posted on 2009-06-29 15:35
Hero 閱讀(235)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //HLOJ 1040 Accepted 31 3716 761 C++
2
3 //分層的動態(tài)規(guī)劃
4 //倒序可能更簡單 -- 避免干擾
5
6 #include <iostream>
7
8 using namespace std ;
9
10 const int size = 30 ;
11 int money[size] ;
12
13 int inn ;
14 int inm ;
15
16 int dp[size][30000] ;
17 int flag[30000] ;
18
19 int main()
20 {
21 /*while( cin >> inn && inn )
22 {
23 memset( dp, 0, sizeof(dp) ) ;
24
25 for( int i=1; i<=inn; i++ ) cin >> money[i] ;
26
27 cin >> inm ;
28
29 dp[0][0] = 1 ;
30 int total = 0 ;
31 for( int i=1; i<=inn; i++ )
32 {
33 for( int j=0; j<=total; j++ )
34 {
35 if( dp[i-1][j] )
36 {
37 dp[i][j] = 1 ;
38 if( j + money[i] <= inm )
39 {
40 dp[i][j+money[i]] = 1 ;
41 }
42 }
43 }
44 total += money[i] ;
45 }
46
47 int ans = 0 ;
48 for( int j=inm; j>=0; j-- )
49 {
50 if( dp[inn][j] )
51 {
52 ans = j ; break ;
53 }
54 }
55
56 printf( "%d\n", ans ) ;
57 }*/
58
59 while( cin >> inn )
60 {
61 for( int i=1; i<=inn; i++ ) cin >> money[i] ;
62 cin >> inm ;
63
64 memset( flag, 0, sizeof(flag) ) ;
65
66 int total = 0 ; flag[0] = 1 ;
67 for( int i=1; i<=inn; i++ )
68 {
69 for( int j=total; j>=0; j-- )
70 {
71 if( flag[j] && j+money[i]<=inm )
72 {
73 flag[j+money[i]] = 1 ;
74 }
75 }
76 total += money[i] ;
77
78 }
79
80 int ans = 0 ;
81 for( int i=inm; i>=0; i-- )
82 {
83 if( flag[i] )
84 {
85 ans = i ; break ;
86 }
87 }
88
89 cout << ans << endl ;
90 }
91
92 return 0 ;
93 }