bitset优化背包

题目：https://agc020.contest.atcoder.jp/tasks/agc020_c

回忆下一题，是零一背包，主要的做法就是凑出最接近sum/2的价值，然后发现现在的背包的容量是2000*2000，物品数量是2000，那么如果你用正常的

数组背包的做法的话，8*10^9的复杂度是会超时的，代码如下：

int n;

    scanf("%d",&n);

    ll sum = ;

    rep(i,,n) scanf("%lld",&a[i]),sum+=a[i];

    dp[] = ;

    rep(i,,n) repd(j,(sum+)/,a[i]) dp[j] = max(dp[j],dp[j-a[i]]);

    repd(i,sum/,) if(dp[i]) return printf("%lld",sum-i),;

    return ;

我们会发现，每个背包的状态要么是零，要么是1，那么我们就可以用bitset来实现速度上的优化：

8*10^9/64,那么这样的话，是符合时间限制的，代码如下：

bitset<maxn> bt;

int main()

{

    int n,a,sum = ;

    scanf("%d",&n);

    bt[] = ;

    rep(i,,n){

        scanf("%d",&a);

        bt |= bt<<a;

        sum += a;

    }

    rep(j,(sum+)/,sum+) if(bt[j]) return printf("%d",j),;

    return ;

}

那么为什么可以用位运算的|(或)呢，因为你看正常的数组做法，

dp[j] = max(dp[j],dp[j-a[i]]);

dpj是从dpj-ai转移过来的，所以减去ai就可以相当于位运算的左移

巴特西

bitset优化背包

最新文章

热门文章