题意

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $s_i$ 件，每件体积为 $v_i$，价值为 $w_i$。求最大总价值。$N,V,s_i \le 1000$。

思路

一句话本质：用二进制分组把每种物品从 $s_i$ 个独立物品压缩成 $O(\log s_i)$ 个"打包物品"，大幅减少 01 背包的物品数量。

上一题的三重循环为什么不够？

$N,V,s$ 都达到 $1000$，$O(N \cdot V \cdot s)$ 约 $10^9$，无法接受。瓶颈在内层循环：每个物品要枚举 $k=1,2,\dots,s_i$ 遍历 $s_i$ 次。

问题的本质是什么？

原来的做法把 $s_i$ 个同种物品拆成 $s_i$ 个独立 01 物品。但 $s_i$ 可能很大，产生过多物品。我们需要一种方式，能用更少的"代表"物品组合出任意不大于 $s_i$ 的选取数量。

怎么用更少的包拼出 $1 \sim s_i$ 的任意数量？

二进制表示告诉我们：任何一个整数都可以唯一表示为若干个 $2$ 的幂之和。于是把 $s_i$ 拆成 $1,2,4,8,\dots,2^p,r$（其中 $r < 2^{p+1}$ 是拆分后剩余的部分），每个段打包成一个新物品：

• 第 $j$ 个包包含 $2^j$ 件原物品，体积 $2^j \cdot v$，价值 $2^j \cdot w$
• 最后若有余数 $r$，再补一个包

例如 $s=13$，拆成 $1+2+4+6$（$6$ 是余数）。任意 $k \le 13$ 都可以用这些包的某个子集拼出来——这等价于 $k$ 的二进制分解。

为什么这样分组后与原问题等价？

原问题允许选 $0 \sim s_i$ 件该物品的任意数量。任意一种选取 $k$ 件的方案，都能唯一对应到若干二进制包的组合；反过来，任意一组二进制包的总原物品数不超过 $s_i$（因为拆分时保证总和 $= s_i$）。所以两者能产生的总价值集合完全相同。

于是算法变为：对每种物品进行二进制拆分，每个包当作一个独立的 01 物品跑标准 01 背包。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * 多重背包问题 II — 二进制分组优化
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2005;
int n, V;
int dp[maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; s > 0; k <<= 1) {
            int cnt = min(k, s);
            s -= cnt;
            int pack_v = cnt * v;
            int pack_w = cnt * w;
            for (int c = V; c >= pack_v; --c)
                dp[c] = max(dp[c], dp[c - pack_v] + pack_w);
        }
    }
    cout << dp[V] << '\n';
    return 0;
}

复杂度

• 时间：每种物品拆出 $O(\log s_i)$ 个包，总物品数 $O(N \cdot \log \max s_i) \approx 10^4$，01 背包 $O(\text{物品数} \cdot V) \approx 10^7$。
• 空间：$O(V)$。

总结

二进制分组是多重背包最经典的优化，核心思想是把"选几个"的问题等价转化为"选哪些二进制包"的问题，把物品数量从 $O(s)$ 压缩到 $O(\log s)$。当数据再大一个量级时（$V \sim 5 \times 10^4$），单调队列是下一步。