题目分析：
对于这种某一个值很大另一个值很小的背包题，就是要求找特殊性质。
既然每一个 \(w\) 都可以写成 \(a \times 2^b\) 的性质，就可以对于每一个 \(b\) 单独做背包，这样的复杂度并不高，这样就可以得到 \(f_{i,j}\) 表示第 \(i\) 位选择 \(j\) 个的最大价值。
对于背包合并其实并不简单，我们可以考虑设 \(g_{i,j}\) 表示考虑了前 \(i\) 位，第 \(i\) 位有 \(j\) 个，且最终的重量的前 \(i-1\) 位不超过 \(W\) 的前 \(i-1\) 位的最大价值。
其实这个状态也就相当于一个背包然后加上了一个重量的限制。
转移其实就是 \(g_{i,j} = \max\{g_{i,k} + f_{i-1,2 \times (j-k) + dig(W,i-1)}\}\) 其中 \(dig(W,i)\) 表示 \(W\) 的第 \(i\) 位是 \(0\) 还是 \(1\)。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int tot[35],w[35][104],v[35][105],f[35][1005],g[35][5005];
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,m;scanf("%lld%lld",&n,&m);
while(n != -1 && m != -1){
for(int i=1; i<=n; i++){
int x,y;scanf("%lld%lld",&x,&y);
int cnt = 31;
while(x % (1<<cnt) != 0) cnt--;
++tot[cnt];
v[cnt][tot[cnt]] = x / (1<<cnt);
w[cnt][tot[cnt]] = y;
}
for(int i=0; i<=30; i++){
for(int j=1; j<=tot[i]; j++){
for(int k=tot[i]*10; k>=0; k--){
if(k - v[i][j] >= 0)
f[i][k] = max(f[i][k],f[i][k-v[i][j]] + w[i][j]);
}
}
}
for(int i=0; i<=tot[0]*10; i++){
g[0][i] = max(g[0][i-1],f[0][i]);
}
for(int i=1; i<=30; i++){
for(int j=0; j<=n*10; j++){
for(int k=0; k<=j; k++){
g[i][j] = max(g[i][j],f[i][k] + g[i-1][2 * (j - k) + ((m >> (i-1)) & 1)]);
}
}
}
int res = 0;
while(m > (1<<res)) ++res;--res;
printf("%lld\n",g[res][1]);
scanf("%lld%lld",&n,&m);
memset(tot,0,sizeof(tot));memset(f,0,sizeof(f));memset(g,0,sizeof(g));
}
return 0;
}