Watashi's BG(01背包思想+深搜+剪枝)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3631

0MS：

View Code

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std ;
 4 int a[31] ;
 5 int n, m, ans ;
 6 void dfs(int i, int v)
 7 {
 8     if(ans==m)
 9     return ;
10     if(v>m)
11     return ;
12     if(i<1)
13     {
14         ans = max(ans, v) ;
15         return ;
16     }
17     int j, sum = v ;
18     for(j=i; j>=1; j--)
19     sum += a[j] ;
20     if(sum<ans)
21     return ;
22     dfs(i-1, v+a[i]) ;
23     dfs(i-1, v) ;
24 }
25 int main()
26 {
27     int i ;
28     while(scanf("%d%d",&n, &m)!=EOF)
29     {
30         for(i=1; i<=n; i++)
31         scanf("%d", &a[i]) ;
32         sort(a+1, a+1+n) ;
33         ans = 0 ;
34         dfs(n, 0) ;
35         printf("%d\n", ans) ;
36     }
37     return 0 ;
38 }

840MS：

View Code

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std ;
 4 int w[31];
 5 int m,n;
 6 int ans;
 7 void dfs( int k, int sum )
 8 {
 9     if( ans == m )
10         return ;
11     if( ans < sum )
12         ans = sum;
13         for( int i=k; i<n&&w[i]+sum<=m; i++ )
14         {
15             dfs( i+1, sum+w[i] );
16         }
17 }
18 int main()
19 {
20     while( scanf( "%d%d", &n,&m ) != EOF )
21     {
22         ans = 0;
23         for( int i=0; i<n; i++ )
24         {
25             scanf( "%d", &w[i] );
26             ans += w[i];
27         }
28         if( ans <= m )
29         {
30             printf( "%d\n", ans );
31         }
32         else
33         {
34             sort( w, w+n );
35             ans = 0;
36             dfs( 0,0 );
37             printf( "%d\n",ans );
38         }
39     }
40     return 0;
41 }