题目链接: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; }
Comments 1 条评论
haihai