[杭电多校1][HDUOJ]7140.Backpack（DP + bitset）

题目链接：Problem - 7140 (hdu.edu.cn)

题目 / Problem

有一个容量为M的背包，有N个物品（体积v，价值w），请问怎样选择可以使得物品恰好装满背包并使得价值的异或和最大。求出最大的异或和。

思路 / Thought

不难想到是一道dp题，状态dp[i][j][k]表示到i个物品为止，异或和为j，体积为k是否能够达到，也就是说dp的值为0或1。

但是这样更新出结果的时间复杂度为O(N ^ 3)，而N最大为1023，显然超时。因为dp值为0或1，可以考虑用bitset并采用位运算来更新，再把i维给压缩掉。这样复杂度就达到了O(N ^ 3 / w)，w一般为64（计算机位数）。

更新的方程为

这个转移方程有些特殊，解读一下，t是一个0或1的值，用于表示i。

每次dp[t][j]可以从dp[t ^ 1][j]直接转移过来，也就是说不拿第i个物品。

也可以从dp[t ^ 1][j ^ w[i]] << v[i]转移过来，其实就相当于dp[t ^ 1][j ^ w[i]][k - v[i]，而这个下标的减法的含义表现在位运算中就是dp[t ^ 1][j ^ w[i]]这个bitset左移v[i]位之后就可以转移到dp[t][j]了。

代码 / Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1030;
int w[maxn], v[maxn];//价值和体积

bitset<maxn> dp[2][maxn];//dp[到i为止][价值异或和j][体积k] 
 
void solve()
{
	int N, M;cin >> N >> M;
	//清空非常重要 
	for(int i = 0;i < 1024; ++ i)dp[0][i].reset(), dp[1][i].reset();
	
	for(int i = 1;i <= N; ++ i)cin >> v[i] >> w[i];
	int t = 1;
	dp[0][0][0] = true;
	for(int i = 1;i <= N; ++ i, t ^= 1)
		for(int j = 0;j < 1024; ++ j)
			dp[t][j] = dp[t ^ 1][j] | (dp[t ^ 1][j ^ w[i]] << v[i]);
	
	int ans = -1;
	for(int i = 1023;i >= 0; -- i)
		if(dp[t ^ 1][i][M])
		{
			ans = i;
			break;
		}
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(0);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}