题意

给出 n 种宝物。第 i 种宝物有：

• 价值 v_i
• 重量 w_i
• 数量 m_i

要求在总重量不超过 W 的前提下，使总价值最大。

思路

一句话本质：二进制拆分将多重背包转成 01 背包——$1,2,4,\dots,2^k,$ 余数这组数可以拼出 $0 \sim m$ 的所有整数。

先看最直接的做法：

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
27import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n, W = data[0], data[1]
items = []
idx = 2
for _ in range(n):
    v, w, m = data[idx], data[idx + 1], data[idx + 2]
    idx += 3
    items.append((v, w, m))

best = 0

def dfs(i, weight, value):
    global best
    if i == n:
        best = max(best, value)
        return
    v, w, m = items[i]
    for k in range(m + 1):
        nw = weight + k * w
        if nw > W:
            break
        dfs(i + 1, nw, value + k * v)

dfs(0, 0, 0)
print(best)

brute.py 对每种物品枚举取 $0 \sim m_i$ 件，递归遍历所有组合。$n$ 最大 $100$，每种物品 $m_i$ 可能很大，组合数 $\prod (m_i+1)$ 爆炸。

暴力为什么不能直接用 01 背包做？

01 背包要求每件物品只能选/不选，但这里每种物品有 $m_i$ 件。如果把每件看作独立物品，总物品数 $=\sum m_i \leqslant 10^5$，直接跑 01 背包就是 $O(W \cdot \sum m_i)$，在这个范围还行但不是最优。

能不能把 $m_i$ 件变成更少的组，每组只选/不选，但拼出所有数量？

这就是二进制拆分的核心：任何整数 $m$ 都可以写成 $1 + 2 + 4 + \dots + 2^k + r$（$r \lt 2^{k+1}$，且 $r$ 最小化保证所有组加起来 $= m$）。这些数的任意子集和可以覆盖 $0 \sim m$ 的每一个整数——原理是二进制表示：$0$ 到 $2^{k+1}-1$ 都可以用低 $k+1$ 位表示，剩余部分由 $r$ 覆盖。

为什么这样正确？

对任意 $x \in [0, m]$，总能用一部分 $1,2,4,\dots,2^k,r$ 的和来表示它。因此原来 01 背包要枚举"取 $x$ 件"的决策，现在等价于"选哪些组"——每组是 $c$ 件打包（重量 $c\cdot w_i$，价值 $c\cdot v_i$），这就是标准的 01 背包。

拆分后怎么做？

对每种物品 $i$，令 $k=1$，每次取 $\min(k, m_i)$ 件打包成一个新的 0/1 物品，$m_i$ 减去这个数，$k$ 翻倍，直到 $m_i=0$。所有打包好的物品做一维 01 背包（容量倒序），$dp_W$ 即答案。总物品数降至 $O(\sum \log m_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#include <bits/stdc++.h>
using namespace std;

const int MAXW = 40005;

int n, W;
// dp[j] 表示容量为 j 时的最大总价值。
int dp[MAXW];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        int v, w, m;
        cin >> v >> w >> m;              // 价值 v，重量 w，数量 m

        // 二进制分组优化多重背包：把 m 拆成 1,2,4,... 的包。
        int k = 1;
        while (m > 0) {
            int use = min(k, m);
            int wv = use * w;            // 包的重量
            int vv = use * v;            // 包的价值
            // 每包作为 0/1 背包物品，倒序枚举。
            for (int j = W; j >= wv; j--) {
                dp[j] = max(dp[j], dp[j - wv] + vv);
            }
            m -= use;
            k <<= 1;
        }
    }

    cout << dp[W] << '\n';
    return 0;
}

复杂度

设拆分后的新物品总数为 M，则总时间复杂度是 $O(W * M)$，空间复杂度是 $O(W + M)$。

总结

这题的关键不是背包状态本身，而是把“每种物品最多选 m_i 件”的限制高效压缩掉。二进制拆分是多重背包里最常用、也最稳的做法。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。