梦幻岛宝珠个人题解

552Hz / 2023-08-03 / 原文

这题的物品数量非常小，但是背包的重量非常大，我们采用压缩到二进制位来考虑，因为最多是n*20的数位*个数，并且上一位dp的状态不影响下一位。所以我们设计当前dp的状态为选取了前i位置时候所能获得的最大值。又因为上一维在数组dp时可能会被上一维的影响所以f[min(2*i+d,s)] =max(f[min(2*i+d,s)],g[i]);来在这一维中更新当前的值。最后再在vector里面跑一下当前维数的背包，最后f[0]就是背包剩余容量为0时的体积

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
const ll inf=1ll<<60;
vector<pair<int,int>>item[40];
ll f[2010],g[2010];
int n,W;
void solve(){
    int s=0;
    for(int i=0;i<=30;i++){
        item[i].clear();
    }
    for(int i=0;i<n;i++){
        int w,v;
        cin>>w>>v;
        int lev=__builtin_ctz(w);
        w>>=lev;
        item[lev].push_back({w,v});
        s+=w;
    }
    for(int i=0;i<=s;i++)f[i]=-inf;
    f[0]=0;
    for(int i=30;i>=0;i--){

        for(int i=0;i<=s;i++) g[i]=f[i],f[i]=-inf;
        int d=(W>>i)&1;
        for(int i=0;i<=s;i++){
            f[min(2*i+d,s)] =max(f[min(2*i+d,s)],g[i]);
        }

        for(int i=s-1;i>=0;i--)
            f[i] =max(f[i],f[i+1]);

        for(auto p:item[i]) {
            for(int i=p.first;i<=s;i++){
                f[i-p.first] =max(f[i-p.first],f[i]+p.second);
            }
        }
    }
    cout<<f[0]<<endl;
}


int main() 
{
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    while(true){
        cin>>n>>W;
        if(n==-1||W==-1){
            break;
        }
        solve();
    }
    return 0;
}