传送门
解题思路
题意很简单，就是一个有特殊条件的01背包：
物品的体积很大，并且可以写成 (a imes 2^b) 的形式。
肯定是从这种特殊限制入手考虑，而且很容易想到按照二进制位分开做。
我们设 (f[i][j]) 表示对体积表示为 (a imes 2^i) 的物品进行01背包，背包的总体积为 ((j imes2^i)) 时的最大价值。
再考虑如何合并每一位。
设 (dp[i][j]) 表示对体积小于等于 (a imes 2^i) 的物品进行01背包，背包总体积为 ((j imes 2^i+W二进制的后i-1位)) 时的最大价值。
换种说法就是dp到了第i位时，保证后i-1位满足W的要求。
因为每一个二进制位为0或者1，所以合并的时候需要考虑低位向高位借位，即第i位每减1，第i-1位就加2。
预处理一个 (num[i]) 表示体积表示为 (a imes 2^i) 的物品的 (a) 的和。
转移方程：
[dp[i][j]=max(dp[i][j],f[i][j-k]+dp[i-1][min(num[i-1],2 imes k+(w>>(i-2)& 1)) ])
]
最后的答案很显然就是 (dp[W的最高位][1])。
注意的细节：
- <<运算符有限度低于+
- 转移方程中的min的原因是有可能转给i-1的2*k太大以至于所有的加起来仍小于2*k，这时候如果用2*k将会数组越界或者返回0（以为没有更新过）
- num[i]在求dp的过程中要动态更新（具体看总代码53行），意义改变为体积小于等于 (a imes 2^i) 的物品的和的a值。
AC代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=105;
int n,m,w[maxn],W[maxn],dp[35][maxn],f[35][maxn],v[maxn],to[35][maxn],num[maxn];
inline int getmax(int x){
int res=0;
while(x>0){
res++;
x>>=1;
}
return res;
}
inline int getmin(int x){
int res=1;
while((x&1)==0){
res++;
x>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
while(1){
memset(dp,0,sizeof(dp));
memset(f,0,sizeof(f));
memset(v,0,sizeof(v));
memset(to,0,sizeof(to));
memset(num,0,sizeof(num));
cin>>n>>m;
if(n==-1&&m==-1) break;
int maxm=getmax(m);
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
int id=getmin(w[i]);
to[id][++to[id][0]]=i;
W[i]=w[i]/(1<<(id-1));
num[id]+=W[i];
}
for(int i=1;i<=maxm;i++){
for(int j=1;j<=to[i][0];j++){
for(int k=num[i];k>=0;k--){
if(k-W[to[i][j]]<0) break;
f[i][k]=max(f[i][k],f[i][k-W[to[i][j]]]+v[to[i][j]]);
}
}
}
for(int i=1;i<=maxm;i++){
num[i]+=(num[i-1]+1)/2;
for(int j=0;j<=num[i];j++){
for(int k=0;k<=j;k++){
dp[i][j]=max(dp[i][j],f[i][j-k]+dp[i-1][min(num[i-1],2*k+(m>>(i-2)&1))]);
}
}
}
cout<<dp[maxm][1]<<endl;
}
return 0;
}