[杭电多校1][HDUOJ]7140.Backpack(DP + bitset)

发布于 2022-07-20  373 次阅读


题目链接: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-22