HDU 3448 Bag Problem

这是一道搜索的背包题目

题意：

有n件物品从中最多选m件，使其总重量不超过v，求能获得的最大重量

有一个很重要的剪枝(是数据的问题还是这个剪枝本身很高效？)：

如果重量最大m件物品都不超过v，则答案就是该m件物品之和；或者最轻的物品的重量大于v则答案为0

中间TLE了几次，又WA了几次，好辛苦啊，Orz

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 LL ans, n, m, v, a[45];
10 bool vis[45];
11 
12 void DFS(LL x, LL cnt, LL w)
13 {
14     if(x > n || cnt > m)    return;
15     if(w > ans)    ans = w;
16     for(int i = x + 1; i <= n; ++i)
17     {
18         if(!vis[i] && a[i] + w <= v)
19         {
20             vis[i] = true;
21             DFS(x + 1, cnt + 1, w + a[i]);
22             vis[i] = false;
23         }
24     }
25 }
26 
27 int main(void)
28 {
29     #ifdef LOCAL
30         freopen("3448in.txt", "r", stdin);
31     #endif
32 
33     while(scanf("%lld%lld", &m, &v) == 2)
34     {
35         scanf("%lld", &n);
36         ans = 0;
37         for(int i = 1; i <= n; ++i)    scanf("%lld", &a[i]);
38 
39         //剪枝
40         sort(a + 1, a + 1 + n);
41         for(int i = n; i > n - m; --i)
42             ans += a[i];
43         if(a[1] > v)    ans = 0;
44         if(ans <= v)
45         {
46             printf("%lld
", ans);
47             continue;
48         }
49         
50         ans = 0;
51         memset(vis, false, sizeof(vis));
52         DFS(0, 0, 0);
53         printf("%d
", ans);
54     }
55     return 0;
56 }

代码君