Compute'sKnapsack

第一行两个整数 n,m $(1 \leq n \leq 34, 0 \leq m \leq 10^9)$ ，分别表示店内商品的个数和背包的容积。

第二行有 n 个整数 $w_1, w_2,\ldots,w_n$ $(1 \leq w_i \leq 10^9)$ ，分别表示 n 件物品的体积。

第三行有 n 个整数 $a_1, a_2,\ldots,a_n$ $(|a_i|\leq 10^9)$ ，分别表示 n 件物品能带给 Compute 的满足度。

C++ 解法, 执行用时: 202ms, 内存消耗: 46604K, 提交时间: 2022-05-03 18:07:58

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=40,M=1e7+5,inf=1e18;
int n,m,w[N],a[N];
struct trie
{
	int ch[M][2],bo[M],tot=0;
	trie(){bo[0]=-inf,tot=0;}
	void insert(int x,int w)
	{
		int u=0;
		for(int i=35;i>=0;i--)
		{
			int v=(x>>i)&1ll;
			if(!ch[u][v]) ch[u][v]=++tot;
			u=ch[u][v];
			bo[u]=max(bo[u],w);
		}
	}
	int ask(int x)
	{
		int u=0,res=-inf;
		for(int i=35;i>=0;i--)
		{
			int a=(x>>i)&1,b=(m>>i)&1;
			if(b) res=max(res,bo[ch[u][a^b^1]]);
			u=ch[u][a^b];
			if(u==0) break;
			if(i==0) res=max(res,bo[u]);
		}
		return res;
	}
}t;
void binary(int x)
{
	vector<int>a;
	while(x)
	{
		a.push_back(x%2);
		x>>=1;
	}
	reverse(a.begin(), a.end());
	for(auto it:a)
		cerr<<it<<" ";
	cerr<<endl;
}
signed main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++) scanf("%lld",&w[i]);
	for(int i=0;i<n;i++) scanf("%lld",&a[i]);
	n=34;
	int res=0;
	for(int j=0;j<(1<<17);j++)
	{
		int cnt=0,sum=0;
		for(int i=0;i<17;i++ )
		{
			if((1<<i)&j)
			{
				cnt^=w[i];
				sum+=a[i];
			}
		}
		if(cnt<=m) res=max(res,sum);
		t.insert(cnt, sum);
	}
	for(int j=0;j<(1<<17);j++)
	{
		int cnt=0,sum=0;
		for(int i=0;i<17;i++)
		{
			if((1<<i)&j)
			{
				cnt^=w[i+17];
				sum+=a[i+17];
			}
		}
		res=max(res,sum+t.ask(cnt));
	}
	cout<<res<<endl;
	return 0;
}

详情