超大背包问题(折半枚举, 双向搜索)

网友投稿 1210 2022-10-14

超大背包问题(折半枚举, 双向搜索)

超大背包问题(折半枚举, 双向搜索)

有重量和价值分别为wi, vi (1 <= wi, vi <= 1e15)的n (1 <= n <= 40)个物品，从中挑选总重不超过W(1 <= W <= 1e15)的物品，求价值总和最大值。

这是典型的01背包问题，不过dp求解复杂度为O(nW)，这里W太大了，因此无法求解。挑选物品方法共有2^n种，也无法直接枚举。但是拆成两半再枚举的话还是可行的，每部分最多只有20个。假设第一部分某个选取方法对应的重量和价值为w1, v1，那么只要在第二部分中寻找w2+w1<=W且v2最大的方法就行了。寻找时可以用二分查找，总时间复杂度为O(2^(n/2)n)，可以接受。

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int maxn = 50;const LL INF = 0x3f3f3f3f;int n;LL w[maxn], v[maxn];LL W;pair ps[1<<(maxn/2)]; // (重量, 价值)void solve(){ //枚举前半部分 int n2 = n / 2; for (int i = 0; i < (1<> j) & 1) { sw += w[j]; sv += v[j]; } ps[i] = make_pair(sw, sv); } //去除多余的元素 sort(ps, ps+(1<> j) & 1) { sw += w[n2 + j]; sv += v[n2 + j]; } if (sw <= W) { LL tv = (lower_bound(ps, ps + m, make_pair(W - sw, INF)) - 1)->second; res = max(res, sv+tv); } } printf("%lld\n", res);}int main(){ while (~scanf("%d%lld", &n, &W)) { for (int i = 0; i < n; ++i) scanf("%lld%lld", &w[i], &v[i]); solve(); } return 0;}/*Sample Input4 52 31 23 42 2Sample Output7*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：方法
上一篇:【每日算法Day 72】谷歌面试题：又双叒叕是位运算，最详细的自动机推导过程...
下一篇:【每日算法Day 94】经典面试题：机器人的运动范围
相关文章

 发表评论

暂时没有评论，来抢沙发吧~