题意

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $s_i$ 件，每件体积为 $v_i$，价值为 $w_i$。求在总容量不超过 $V$ 的前提下能获得的最大总价值。$N,V,s_i \le 100$。

思路

一句话本质：把每种物品的 $s_i$ 件"展平"成 $s_i$ 个独立的 01 物品，每个物品选或不选。

最直接的做法是什么？

对每种物品枚举选取件数 $k$（$0 \le k \le s_i$）。brute.py 正是这样做的——DFS 枚举每种物品选几个，复杂度 $O(\prod s_i)$，指数级，不可行。

既然选 $k$ 件等价于"选 $k$ 个同种物品"，能不能把它们当成 $k$ 个独立物品分别决策？

可以。因为每件物品之间没有依赖关系——选第 $j$ 件不影响选第 $j+1$ 件的代价和收益。所以把 $s_i$ 个相同物品当成 $s_i$ 个彼此独立的 01 物品来处理，完全等价。

这就得到了三重循环：

• 外层遍历每种物品
• 中层容量 $c$ 从 $V$ 倒序到 $0$（01 背包要求倒序，防止同一轮中重复选取同一物品的多个"展平"副本）
• 内层枚举选取件数 $k$，更新 $dp[c] = \max(dp[c], dp[c-k \cdot v] + k \cdot w)$

为什么容量循环必须倒序？

这和标准 01 背包完全一样。如果正序，已经更新过的 $dp[c]$ 可能在这一轮中被"后代"状态再次引用，导致同一物品被多次使用——而我们通过"展平"已经把 $s_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/**
 * 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
 * 多重背包问题 I — N≤100 V≤100 s_i≤100，直接三重循环DP
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 105;
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 c = V; c >= 0; --c)
            for (int k = 1; k <= s && k * v <= c; ++k)
                dp[c] = max(dp[c], dp[c - k * v] + k * w);
    }
    cout << dp[V] << '\n';
    return 0;
}

复杂度

• 时间：$O(N \cdot V \cdot \max s_i)$，最坏 $100 \times 100 \times 100 = 10^6$，轻松通过。
• 空间：$O(V)$，滚动数组。

总结

多重背包最朴素的做法就是把每个物品拆成 $s_i$ 个 01 物品跑三次循环。数据小的时候这已经足够，但 $s_i$ 一旦变大（比如 $10^4$），就需要二进制分组或单调队列进一步优化。