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;
}