首页 > 代码库 > 超大背包问题
超大背包问题
题意:
有重和价值分别为wi,vi的n个物品。从这些物品中挑选出总质量不超过W的物品,求所有挑选出的方案中价值总量的最大值。
限制条件:1<=n<=40
1<=wi,vi<=10^15
1<=W<=10^15
思路:
此题如果用动态规划求解复杂度为O(nW),故不划算。
可以考虑折半搜索的方法,将所有的n个物品划分成数量对等的两部分,先穷举第一部分的每一种选取物品的情况,记录好每一种情况下的物品的重量w1和价值v1,之后进行挑选,挑选出性价比高的组合,
即如果选取两种情况有如下比较:w1[i]<=w1[j]且v1[i]>=v1[j],那说明情况i的组合总重量小并且价值又高,完全优于j,就可以把情况j给排除。
这样一来第一部分的所有情况经过筛选排序就会满足w1[i]<w1[j]且v1[i]<v1[j].
接下来再对第二部分进行枚举,对于第二部分枚举出来的每一种情况,都可以计算出相应的W-w2,其意义就是在第二部分选定了相应物品的情况下,可以继续装入的物品质量还剩下W-w2,那么剩下的这些质量要用第一部分尽可能
多的物品来填充,这时可以进行二分查找,找出一种组合,使得该组合的总质量小于等于W-w2且最接近于W-w2。穷举第二部分的所有情况,最终可以得到最优的价值总和!
代码:
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N_MAX = 40 + 2; int n; ll W; ll w[N_MAX], v[N_MAX]; struct goodss { ll first, second; goodss(){} goodss(ll a,ll b):first(a),second(b){} bool operator <(const goodss&b)const { return first < b.first; } }; goodss goods[1 << (N_MAX / 2)]; int main() { while (cin>>n) { for (int i = 0; i < n; i++) cin >>w[i]; for (int i = 0; i < n; i++) cin >>v[i]; cin >> W; for (int i = 0; i < 1 << (n / 2); i++) {//对于每一种情况而言 ll w_sum = 0, v_sum = 0; for (int j = 0; j < (n / 2); j++) { if (i&(1 << j)) { w_sum += w[j];////!!!!!!!!! v_sum += v[j]; } } goods[i] = goodss(w_sum,v_sum); } //去除一些性价比低的元素 sort(goods,goods+(1<<(n/2))); int m = 1; for (int i = 1; i < (1 << (n / 2));i++) { if (goods[m - 1].second < goods[i].second) {//说明满足条件,筛选下来 goods[m++] = goods[i]; } } ll res = 0; for (int i = 0; i < 1 << (n - n / 2); i++) {//对于每一种情况得到的sum_v,都可以通过二分搜索唯一的找到一个不大于W-sum_w的max_w ll sum_v=0, sum_w = 0; for (int j = 0; j < (n - n / 2); j++) { if (i&(1 << j)) { sum_w += w[j + n / 2]; sum_v += v[j + n / 2]; } } if (sum_w <= W) {//!!已经取得的物品重量不能超过W ll max_v; if (W-sum_w >= goods[0].first) {//最多能够取入的重量太小的话,那么剩下的物品都将无法取得 goodss* tmp = lower_bound(goods, goods + m, goodss(W - sum_w, INT_MAX)); if (tmp->first > (W - sum_w)) { tmp--; } max_v = tmp->second; } else max_v = 0;//没法从剩余的物品中取得物品放入包中 res = max(res,max_v+sum_v); } } cout << res << endl; } return 0; }
超大背包问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。