链接
按 (b) 分组 (dp)，最后合并时：
f[i][j]=max(f[i][j],f[i][j-k]+f[i-1][min(w[i-1],k<<1|(m>>i-1&1))]);
表示容量为 (j cdot 2^i + （m) & (2^i-1))，分 (j-k) 个给 (i) 组，分 (2k) 个给 (i-1) 组的最大价值。
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pb push_back
using namespace std;
const int N=35,M=1e3+10;
struct hh{
int cos,val;
};
int n,m,f[N][M],w[N];
vector<hh>a[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
int main()
{
int x,y,len;
while(n=in(),m=in(),~n){
memset(f,0,sizeof(f));
memset(w,0,sizeof(w));
for(int i=0;i<=30;++i) a[i].clear();
for(int i=1;i<=n;++i){
x=in(),y=in(),len=0;
while(~x&1) x>>=1,++len;
a[len].pb((hh){x,y}),w[len]+=x;
}
len=0;while((m>>len)^1) ++len;
for(int i=0;i<=len;++i)
for(int k=0;k<a[i].size();++k)
for(int j=w[i];j>=a[i][k].cos;--j)
f[i][j]=max(f[i][j],f[i][j-a[i][k].cos]+a[i][k].val);
for(int i=1;i<=len;++i){
w[i]+=w[i-1]+1>>1;
for(int j=w[i];~j;--j)
for(int k=0;k<=j;++k)
f[i][j]=max(f[i][j],f[i][j-k]+f[i-1][min(w[i-1],k<<1|(m>>i-1&1))]);
}
printf("%d
",f[len][1]);
}
return 0;
}