超大背包问题(二进制枚举 + 二分)

超大背包问题

第一次看到这一题好像是在某一场比赛，就是给你一个炸空间和时间的背包，让你选最大的价值，看似是01背包 然鹅今天在挑战程序设计这本书上看到了这题，看到了作者的做法，感觉豁然开朗，直接暴搜也会炸，但是我们 可以把这些物品拆分成两堆，然后我们用二进制枚举两个堆的物品，时间复杂度为\(O(n*2^{(n/2)})\) 在枚举第二堆的时候我们就可以在第一个堆里通过二分搜索找到满足条件物品堆，然后选择最优的结果就行 每次二分查询时间log(m),m表示的是第一堆物品有效个数，具体请看代码讲解

#include
#include
#include
using namespace std;

const int N = 45;
typedef long long ll;
ll w[N],v[N],W;
int n;

struct Node {
	ll w,v;
}ps[1  b.v;
}

int erfen(int l,int r,ll k) {//二分搜索
	while(l + 1 < r) {
		int mid = l + r >> 1;
		if(ps[mid].w  j & 1) {//是否选取
				tempw += w[j];
				tempv += v[j];
			}
		}
		ps[i] = (Node){tempw,tempv};
	}
	sort(ps,ps+(1