题目
在 \(n(0\leq n \leq 100)\) 个物品中，选择重量不超过 \(W(1\leq W \leq 2^{30})\) 的物品，是所选物品的总价值最大.
物品的重量 \(w_i\) 可以写成 \(a \times 2^{b} (1\leq a \leq 10,0\leq b \leq 30)\).
物品的价值 \(v_i(1\leq v_i \leq 2^{30})\).
思路
通过 \(w_i\) 可以写成 \(a \times 2^{b} (1\leq a \leq 10,0\leq b \leq 30)\) ,很容易想到通过 \(b\) 分层做, 同一层之间的合并是非常简单的01背包.
当前层转移到下一层是这道题的难点.
定义 \(f_{ij}\) 表示背包剩余的容量为 \(j \times 2^i\) 时的最大价值.
观察 \(a \times 2^{i+1}\) 与 \(a \times 2^ i\) 它们属于不同的两层, \(a \times 2^{i+1}\) 可以写成 \(2 \times a \times 2^i\) 这表示了 \(f[i][2a] = f[i+1][a]\) 它们表示的容量相同.
接下来考虑总重量 \(W\) 在层与层之间转移的限制.
我们从高位枚举 \(W\) 时, \(W\) 的第 \(i\) 位为 1 时,转移到第 \(i\) 层的状态为 \(2 \times a + 1\) ,第 \(i\) 位为 0 时, 转移到第 \(i\) 层的状态为 \(2 \times a + 0\).
第 \(i\) 层 从第 \(i+1\) 层转移过来要加上 \(W\) 自身的容量, \(W\) 的第 \(i\) 位为 1 时要加上 \(2^i\).
每一层在最坏情况下物品重量和不超过 1000 ,当转移过来的容量大于 1000 时就没必要保存了，因为剩余 \(1000 \times 2^i\)是可以把剩下的物品都取完的.
int d = (W >> i) & 1;
f[i][min(2 * j + d,1000)] = std::max(f[i][min(2 * j + d,1000)],f[i+1][j]);
因为是从高位开始枚举的，会存在许多不合法的状态，令初值全部为负无穷，f[31][0] = 0.
答案为f[0][0]，背包没有剩余空间的最大值.
可以通过滚动数组优化掉 \(i\) .
代码
const i64 inf = 1LL << 60;
int n;
std::vector<std::pair<int,int>> item[32];
i64 W,f[2010],g[2010];
inline std::pair<int,int> count0(int x){
int lev = 0;
for(;!(x & 1);){
lev++;
x>>=1;
}
return {lev,x};
}
inline void solve(){
int s = 0;
for(int i = 0;i<=30;++i) item[i].clear();
for(int i = 1;i<=n;++i){
int w,v;
std::cin>>w>>v;
auto [lev,x] = count0(w);
item[lev].push_back({x,v});
s+=x;
}
for(int i = 0;i<=s;i++) f[i] = -inf;
f[0] = 0;
for(int i = 30;i>=0;--i){
for(int j = 0;j<=s;j++)
g[j] = f[j],f[j] = -inf;
int d = (W >> i) & 1;
for(int j = 0;j<=s;j++){
f[std::min(s,2 * j + d)] = std::max(f[std::min(s,2 * j +d)],g[j]);
}
for(auto [w,v]:item[i]){
// 一般背包求用了多少空间的最大值
// 这里表示剩余多少空间的最大值
for(int j = w;j<=s;j++)
f[j-w] = std::max(f[j-w],f[j]+v);
}
}
std::cout<<f[0]<<"\n";
}
