注意到 $a,b$ 不大
考虑对每一个 $a*2^b$ 的 $b$ 分别背包
设 $f[i][j]$ 表示只考虑 $b=i$ 的物品时，容量为 $j= sum a$ 的最大价值
这个就是普通的 $01$ 背包
考虑把 $f[i][j]$ 之间合并起来，为了得到容量为 $W$ 时的答案，我们要把 $f$ 的含义稍微变化一下
变成 $f[i][j]$ 表示当前考虑了 $b=2^1$ 到 $b=2^i$ 时的物品，容量为 $j*2^i$ 加上 $W$ 二进制下前 $i-1$ 位的值，此时的最大价值
考虑用 $f[i-1][]$ 更新 $f[i][j]$，枚举总体积为 $(j-k)*2^i$ 的 $b=2^i$ 的物品的最大价值（$f[i][j-k]$）
加上总体积为 $2k*2^{i-1}$ 的 $b<2^i$ 的物品的最大价值 （$f[i-1][k*2]$），注意我们还要考虑 $W$ 的容积，所以设 $W$ 第 $i-1$ 位为 $p$
那么转移为 $f[i][j]=f[i][j-k]+f[i-1][ min(sw[i-1],k*2+p) ]$，此时 $sw[i]$ 表示第 $b<=2^i$ 时物品的体积和上取整为 $2^{sw[i]}$
注意上面枚举 $j$ 的时候要从大到小枚举
转移的细节挺多的...，最终答案即为 $f[m][1]$， $m$ 表示 $W$ 的最高位
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=107,M=1007; int n,W,m,sw[37]; struct Orb{ int val,w; }; vector <Orb> V[37]; ll f[37][M]; int main() { while(233) { n=read(),W=read(); int w,v; if(n==-1&&W==-1) break; for(int i=0;i<=31;i++) V[i].clear(),sw[i]=0; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { w=read(),v=read(); int cnt=0; while(!(w&1)) w>>=1,cnt++; V[cnt].push_back((Orb){v,w}); sw[cnt]+=w; } int t=1,cnt=0; while(t<=W) t<<=1,cnt++; m=cnt-1; for(int i=0;i<=m;i++) { int len=V[i].size(); for(int j=0;j<len;j++) for(int k=sw[i];k>=V[i][j].w;k--) f[i][k]=max(f[i][k],f[i][k-V[i][j].w]+V[i][j].val); } // f[i][j]=f[i][j-k]+f[i-1][ (k<<1) | ( (W>>(i-1)) &1) ] for(int i=1;i<=m;i++) { sw[i]+=(sw[i-1]+1)>>1; int p=(W>>(i-1))&1; for(int j=sw[i];j>=0;j--) for(int k=0;k<=j;k++) f[i][j]=max(f[i][j],f[i][j-k]+ f[i-1][min(sw[i-1],(k<<1)|p)] ); } printf("%lld ",f[m][1]); } return 0; }