2022“杭电杯”中国大学生算法设计超级联赛(1)1003 Backpack 题解
2022/7/23 14:22:55
本文主要是介绍2022“杭电杯”中国大学生算法设计超级联赛(1)1003 Backpack 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2022“杭电杯”中国大学生算法设计超级联赛(1)1003 Backpack 题解
关于我对这题看法:这题考察的算法是动态规划dp,当时开场1小时就有100多支队伍出来,然后我去开这题,
20多分钟就做出来了,所以当时我就以为这大概就是签到题,但是即使5小时结束后,
这题通过队伍数也才200多(大概接近铜牌题了qwq),所以这题有一个特点,就是考察dp的硬知识,
不会就是不会,如果不擅长dp的话想满5个小时也不一定能做出来,而最快的队伍甚至有不到5分钟就切掉的,所以这题是真的只有会和完全不会的。
接下来介绍一种我当时的做法,和题解不同。
题意
给你一个容量为\(m\)的背包和\(n\)个物品,每个物品有体积\(v\)和价值\(w\),求恰好装满背包时物品总的\(XOR\)异或和最大值。
思路
这道题显然一眼\(01\)背包,只是把加换成了异或,所以就不能用\(01\)背包的\(max\)转移做法了,要换思路,但本质还是\(dp\)
先介绍官方题解的思路,是\(bitset+dp\),复杂度\(O(n^3/64)\),其中\(dp[0/1][i][j]\)表示权值\(xor\)和为\(i\),体积和为\(j\)的方案是否存在,
然后体积加\(a[i]\)变成\(<<a[i]\),用\(bitset\)去压位表示异或的状态,可以优化复杂度,否则\(O(n^3)\)会超时。具体的实现就不详细介绍了。
然后介绍一下我当时的做法。
总的思路是二维01背包
首先拿到这种背包题,我的第一个想法就是设状态,然后列状态转移方程,但是普通的01背包只有1维,并且在异或的时候,
当前状态的最大值并不能保留到最后,当前状态不是最大值也可能最后成为最大值,这与01背包的求和相加不同,所以我的想法是给01背包增加一维。
用f[i][j]表示恰好装满i体积背包第j种情况的异或值,同时增加一个\(b[i]\)数组用来记录装满\(i\)体积背包的情况种数,
这样就可以枚举每种情况来转移状态,对于每种情况,状态转移方程如下
$\large{f[j][b[j]]=max(f[j][b[j]],f[j-v[i]][k]}$ ^ $\large{w[i])}$
其中\(b[j]\)表示的是装满\(j\)容量第\(b[j]\)种情况,\(k\)是枚举情况的参数,然后取最大值即可。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll t,n,m,f[1100][1100],v[1100],w[1100],b[1100]; signed main() { ios::sync_with_stdio(false); cin>>t; while(t--) { cin>>n>>m; for(ll i=0;i<=m;++i)for(ll j=0;j<=1050;++j)f[i][j]=-1; for(ll i=0;i<=1050;++i)b[i]=1; for(ll i=1;i<=n;++i)cin>>v[i]>>w[i]; f[0][1]=0; for(ll i=1;i<=n;++i) for(ll j=m;j>=v[i];--j) { ++b[j]; for(ll k=1;k<=b[j-v[i]];++k) f[j][b[j]]=max(f[j][b[j]],f[j-v[i]][k]^w[i]); if(f[j][b[j]]<0)f[j][b[j]]=-1; } ll ans=-1; for(ll i=1;i<=b[m];++i)ans=max(ans,f[m][i]); cout<<ans<<endl; } return 0; }
这篇关于2022“杭电杯”中国大学生算法设计超级联赛(1)1003 Backpack 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升