ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年7月20日 244点热度 1人点赞 1条评论

题目链接: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP hduoj 动态规划 思维 算法竞赛
最后更新:2022年7月22日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

  • 嫩爹

    haihai

    2022年7月22日
    回复
  • 取消回复

    Eriktse

    18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

    文章目录
    • 题目 / Problem
    • 思路 / Thought
    • 代码 / Code

    友情链接 | 站点地图

    COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

    Theme Kratos | Hosted In TENCENT CLOUD

    赣ICP备2022001555号-1

    赣公网安备 36092402000057号