📦 多重背包（Multiple Knapsack）

一、问题模型

有 N 种物品和容量为 V 的背包。第 i 种物品最多有 sᵢ 件，每件体积 vᵢ，价值 wᵢ。

求体积总和 ≤ V 时的最大价值。

三种背包核心区别：

类型	可选次数	内层循环方向	转移关键
01 背包	1 次	倒序	dp[i-1][j-v[i]]
完全背包	无限次	正序	dp[i][j-v[i]]
多重背包	最多 sᵢ 次	见下文	需要枚举个数

---

二、二维写法（朴素）

状态定义

dp[i][j]：考虑前 i 种物品，背包容量为 j 时的最大价值。

转移方程

不选第 i 种物品：

dp[i][j] = dp[i-1][j]

选第 i 种物品的 k 个（k = 1, 2, ..., sᵢ）：

dp[i][j] = max(dp[i][j], dp[i-1][j - k*v[i]] + k*w[i])

（需满足 j ≥ k × v[i]）

代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
int v[110], w[110], s[110];
int dp[110][110];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];  // 不选
            for (int k = 1; k <= s[i]; k++) {  // 选 k 个
                if (j >= k * v[i])
                    dp[i][j] = max(dp[i][j],
                                   dp[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

复杂度：O(N × V × Σsᵢ)

适用范围：N, V, s ≤ 100

---

三、一维写法（朴素，滚动数组）

优化思路

dp[i][j] 只依赖 dp[i-1][...]，可压缩为一维。体积必须倒序枚举，防止同一件物品被重复使用。

代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
int dp[1010];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = m; j >= v; j--)         // 倒序！
            for (int k = 1; k <= s; k++)     // 枚举选几个
                if (j >= k * v)
                    dp[j] = max(dp[j], dp[j - k * v] + k * w);
    }
    cout << dp[m] << endl;
    return 0;
}

问题：内层有三重循环，当 s 很大时会超时 → 需要优化。

---

四、二进制优化 ⭐ 最常用

核心思想

将 sᵢ 件物品用 2 的幂次 拆分，使枚举次数从 O(sᵢ) 降到 O(log sᵢ)。

拆分方法

以 s = 10 为例：

10 = 1 + 2 + 4 + 3
         ↑
     剩余部分单独一组

拆成 4 个"打包物品"：拿 1 件、拿 2 件、拿 4 件、拿 3 件。

通过这 4 个组合，可以凑出 1~10 的任意数量。

拆分模板

int k = 1;
while (k <= s) {
    // 打包 k 个体积为 v、价值为 w 的物品
    items.push_back({k * v, k * w});
    s -= k;
    k *= 2;
}
if (s > 0)
    items.push_back({s * v, s * w});

完整代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
int dp[2010];

struct Item {
    int v, w;  // 打包后的体积、价值
};

int main() {
    cin >> n >> m;

    vector<Item> items;

    // 二进制拆分
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;

        int k = 1;
        while (k <= s) {
            items.push_back({k * v, k * w});
            s -= k;
            k *= 2;
        }
        if (s > 0)
            items.push_back({s * v, s * w});
    }

    // 01 背包（每个打包物品只能选一次）
    for (auto &item : items)
        for (int j = m; j >= item.v; j--)
            dp[j] = max(dp[j], dp[j - item.v] + item.w);

    cout << dp[m] << endl;
    return 0;
}

复杂度：O(N × V × log Σsᵢ)

适用范围：N ≤ 1000, V ≤ 2000, s ≤ 2000

---

五、三种解法对比

方法	时间复杂度	适用场景
二维朴素	O(NVΣs)	数据小，理解原理
一维朴素		数据小，节省空间
二进制优化	O(NV·log Σs)	最常用，推荐

---

六、典型例题

例题（模板·多重背包）

输入：

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出：

10

解释：

• 物品 1：体积 1，价值 2，最多 3 件
• 物品 2：体积 2，价值 4，最多 1 件
• 物品 3：体积 3，价值 4，最多 3 件
• 物品 4：体积 4，价值 5，最多 2 件

最优方案：物品 1 取 2 件（v=2, w=4）+ 物品 2 取 1 件（v=2, w=4）+ 物品 3 取 0 件 + 物品 4 取 0 件 → 总体积 4，总价值 8；或物品 2 + 物品 3 = 体积 5，价值 8。

---

七、与混合背包的关系

多重背包是混合背包的一部分：

s 值	背包类型	循环方向
s = -1	01 背包	倒序
s = 0	完全背包	正序
s > 0	多重背包	二进制拆分后倒序

---

八、记忆口诀

多重物品有上限，二进拆分最擅长；
一拆 log 件物品，01 背包一遍过。