根据题意，很明显需要把a*2^b中b相同的先分成一组，然后首先得到这一组中的答案。
然后如果令f[m]表示当重量为m时的最大值，那么考虑将第k组加入其中，由于第k组的重量一定<=1000*2^k，可以发现只有m的二进制中的10位左右会受到影响。然后dp就好了。
AC代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1105
using namespace std;
int n,m,len,a[105][N],b[105][N],f[35][N],p[35],w[35];
int main(){
while (~scanf("%d%d",&n,&m) && n!=-1 && m!=-1){
int i,j,k; memset(f,0,sizeof(f)); len=0;
memset(p,0,sizeof(p)); memset(w,0,sizeof(w));
for (i=1; i<=n; i++){
int x; scanf("%d",&x); j=0;
while (!(x&1)){ j++; x>>=1; }
a[j][++p[j]]=x; w[j]+=x;
len=max(len,j); scanf("%d",&b[j][p[j]]);
}
for (i=0; i<=len; i++)
for (j=1; j<=p[i]; j++)
for (k=w[i]; k>=a[i][j]; k--) f[i][k]=max(f[i][k],f[i][k-a[i][j]]+b[i][j]);
while (m>>len) len++; len--;
for (i=1; i<=len; i++){
w[i]+=(w[i-1]+1)>>1;
for (j=w[i]; j>=0; j--)
for (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\n",f[len][1]);
}
return 0;
}
by lych
2016.3.17