数位背包-梦幻岛宝珠

(Updated: )
CP
,

题目

P3188 [HNOI2007]梦幻岛宝珠

在 $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$是可以把剩下的物品都取完的.

1
2
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$ .

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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";
}