超大背包问题
输入条件:\(1\le n\le40,1\le w_i,v_i\le10^{15},1\le W\le 10^{15}\)
解法:因为不能够再像前面的背包问题一样,把背包容量作为状态来储存了,因为开不了那么大的空间,那么就应该好好利用 n 很小的这个优势,但是如果全部遍历的话,复杂度就是\(O(2^n)\)很明显这也不能跑完,但是我们可以利用折半枚举,来降低其复杂度,这样复杂度就只有\(O(2^{n/2}n)\)了。
// Created by CAD on 2020/2/2.
#include <bits/stdc++.h>
#define se second
#define INF 0x7fffffffffffffff
#define pll pair<long long,long long>
#define ll long long
using namespace std;
const int maxn=45;
ll w[maxn],v[maxn];
ll W;
pll p[1<<(maxn/2)];
int main()
{
int n; cin>>n>>W;
for(int i=1;i<=n;++i)
cin>>w[i]>>v[i];
int n1=n/2;
for(int i=0;i<1<<n1;++i){
ll sw=0,sv=0;
for(int j=0;j<n1;++j)
if(i>>j&1) sw+=w[j],sv+=v[j];
p[i]={sw,sv};
}
sort(p,p+(1<<n1));
int m=1;
for(int i=0;i<1<<n1;++i)
if(p[m-1].se<p[i].se) p[m++]=p[i];
ll ans=0;
for(int i=0;i<1<<(n-n1);++i)
{
ll sw=0,sv=0;
for(int j=0;j<n-n1;++j)
if(i>>j&1) sw+=w[n1+j],sv+=v[n1+j];
if(sw<=W){
ll t=(lower_bound(p,p+m,make_pair(W-sw,INF))-1)->se;
ans=max(ans,sv+t);
}
}
cout<<ans<<'\n';
return 0;
}