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