首页 > 代码库 > HDU 3448 Bag Problem

HDU 3448 Bag Problem

2024-07-21 18:35:50   211人阅读

这是一道搜索的背包题目

题意：

有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 LOCAL30         freopen("3448in.txt", "r", stdin);31     #endif32 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\n", ans);47             continue;48         }49         50         ans = 0;51         memset(vis, false, sizeof(vis));52         DFS(0, 0, 0);53         printf("%d\n", ans);54     }55     return 0;56 }
代码君

 

HDU 3448 Bag Problem


联系
我们