【GESP】C++六级练习 luogu-B2173, 多重背包

GESP C++六级练习。多重背包DP模板题，是在 01 背包和完全背包基础上的进阶。每种物品有有限的件数限制，介于"最多1件"和"无限件"之间，需要掌握朴素枚举和二进制拆分两种解法。难度⭐⭐。洛谷难度等级普及-。

B2173 多重背包

题目要求

题目描述

你有一个容量为 $V$ 的背包，以及 $n$ 种物品。第 $i$ 种物品的体积为 $w_i$，每件价值为 $val_i$，最多有 $c_i$ 件。

你可以选择每种物品若干件放入背包，但同一种物品选择的件数不能超过 $c_i$，且总容量不能超过 $V$。

请你求出在不超过背包容量的前提下，能获得的最大总价值。

形式化题意：设第 $i$ 种物品选择 $x_i$ 件，则需要满足： $\sum_{i=1}^{n} x_i \cdot w_i \le V,\quad 0 \le x_i \le c_i$ 最大化目标： $\max \sum_{i=1}^{n} x_i \cdot val_i$

输入格式

第一行两个整数 $n, V$，表示物品种类数与背包容量。

接下来 $n$ 行，每行三个整数 $w_i, val_i, c_i$，分别表示第 $i$ 种物品的体积、价值与最多件数。

输出格式

输出一个整数，表示最大总价值。

输入输出样例 #1

输入 #1

3 10
3 4 2
4 5 3
2 3 4

输出 #1

14

说明/提示

样例解释 #1

一种可行的最优方案是：

• 选第 1 种物品 $2$ 件：体积 $2 \times 3 = 6$，价值 $2 \times 4 = 8$
• 选第 3 种物品 $2$ 件：体积 $2 \times 2 = 4$，价值 $2 \times 3 = 6$

总容量 $6 + 4 = 10 \le 10$，总价值 $8 + 6 = 14$，为最大值。

数据范围

对于 $40\%$ 的数据，$1\le n \le 9$，$1\le V \le 1000$，$1\le c_i \le 5$。

对于 $100\%$ 的数据，$1\le n \le 500$，$1\le V \le 1000$，$1\le c_i \le 100$。

题目分析

本题是多重背包问题的标准模板题。如果你已经掌握了 01 背包（P1048 采药）和完全背包（B2174），那么多重背包就是两者之间的"中间地带"：

多重背包的核心难点在于：每种物品既不是只有 1 件，也不是无限件，而是有一个上限 $c_i$。不能简单地套用 01 背包或完全背包的遍历方向，需要额外处理件数限制。

1. 解法一：朴素三重循环（直接枚举件数）

最直观的思路是：对每种物品，枚举选 0 件、1 件、2 件……直到 $c_i$ 件，在所有合法方案中取最大值。

状态定义

$dp[j]$ 表示：背包容量为 $j$ 时，能获得的最大总价值。

状态转移方程

对于第 $i$ 种物品（体积 $w_i$，价值 $val_i$，最多 $c_i$ 件），对每个容量 $j$（从 $V$ 到 $w_i$，逆序）：

$dp[j] = \max_{0 \le k \le c_i,\ k \cdot w_i \le j}\{dp[j - k \cdot w_i] + k \cdot val_i\}$

其中 $k$ 表示第 $i$ 种物品选取的件数。

为什么要逆序遍历？

这里使用的是逆序遍历（和 01 背包一样）。原因是：我们在最内层循环中手动枚举了件数 $k$，已经完整地考虑了"选 0 到 $c_i$ 件"的所有情况。因此需要确保 $dp[j - k \cdot w_i]$ 读到的是上一轮（尚未考虑第 $i$ 种物品时）的旧值，否则同一种物品会被多算。

换句话说：逆序遍历保证了"选几件"的决策由我们的 $k$ 循环精确控制，而不会因为正序遍历产生的"叠加效应"而失控。

复杂度分析

• 时间复杂度：$O(n \times V \times \max(c_i))$。三层循环：$n$ 种物品 × 容量 $V$ × 最多 $c_i$ 件
• 空间复杂度：$O(V)$，一维滚动数组

本题数据范围：$n \le 500, V \le 1000, c_i \le 100$，最坏约 $5 \times 10^7$，在时间限制内可以通过。

2. 解法二：二进制拆分优化

朴素解法在数据范围更大时可能超时。二进制拆分是多重背包的经典优化技巧，核心思想是：把 $c_i$ 件相同物品拆分成若干"捆"，每捆是 1、2、4、8……件，然后对这些"捆"做 01 背包。

为什么二进制拆分是正确的？

任意一个非负整数都可以用若干个不重复的 2 的幂次之和来表示（这就是二进制表示的本质）。例如 $c_i = 13$：

$13 = 1 + 2 + 4 + 6$

我们把 13 件物品拆分成 4 捆：1 件、2 件、4 件、6 件（最后一捆是余数 $13 - 1 - 2 - 4 = 6$）。

对于每一捆，我们只需要决定"选"或"不选"（01 背包），而通过这 4 捆的不同选取组合，可以精确地表示 $0$ 到 $13$ 之间的任意件数：

这样，原本需要枚举 $c_i$ 次的内层循环，被压缩到了 $\lfloor \log_2 c_i \rfloor + 1$ 个"虚拟物品"的 01 背包，大幅减少计算量。

拆分规则

对于 $c_i$ 件物品，按如下方式拆分：

1. 依次拆出 $1, 2, 4, 8, \ldots$ 件的捆，直到剩余件数不足下一个 2 的幂次
2. 把剩余件数作为最后一捆

例如 $c_i = 10$：拆分为 $1, 2, 4, 3$（因为 $1 + 2 + 4 = 7$，剩余 $10 - 7 = 3$）。

每一捆的体积和价值相应地乘以捆内件数，然后作为一个独立的"虚拟物品"参与 01 背包。

复杂度分析

• 时间复杂度：$O(V \times \sum \log_2 c_i)$，远优于朴素解法
• 空间复杂度：$O(V)$

样例验证

样例输入：$n = 3, V = 10$

以朴素解法为例，处理完所有物品后 DP 数组的最终结果：

最终 $dp[10] = 14$，对应选择物品 $1$ 取 $2$ 件（体积 $6$，价值 $8$）+ 物品 $3$ 取 $2$ 件（体积 $4$，价值 $6$），与样例输出一致。

示例代码

方法一：朴素三重循环

通过逆序遍历容量 + 枚举件数 $k$，直接实现多重背包。思路最直观，适合初学者理解。

#include <iostream>
#include <algorithm>

// dp[j] 表示背包容量为 j 时能获得的最大总价值
int dp[1005];

int main() {
    int n, V;
    std::cin >> n >> V;

    // 外层循环：枚举每一种物品
    for (int i = 0; i < n; i++) {
        int w, val, c;
        std::cin >> w >> val >> c;

        // 中层循环：逆序遍历容量（与 01 背包相同）
        // 逆序保证 dp[j - k*w] 读到的是上一轮的旧值
        for (int j = V; j >= w; j--) {
            // 内层循环：枚举第 i 种物品选取的件数 k（从 1 到 c）
            // k=0 对应"不选"，dp[j] 保持不变，无需显式处理
            for (int k = 1; k <= c && k * w <= j; k++) {
                dp[j] = std::max(dp[j], dp[j - k * w] + k * val);
            }
        }
    }

    // dp[V] 即为背包容量为 V 时的最大总价值
    std::cout << dp[V] << std::endl;
    return 0;
}

方法二：二进制拆分优化

将每种物品的 $c_i$ 件按二进制拆分为若干"捆"，转化为 01 背包问题求解。在数据范围较大时效率更优。

#include <iostream>
#include <algorithm>

// dp[j] 表示背包容量为 j 时能获得的最大总价值
int dp[1005];

int main() {
    int n, V;
    std::cin >> n >> V;

    for (int i = 0; i < n; i++) {
        int w, val, c;
        std::cin >> w >> val >> c;

        // 二进制拆分：将 c 件物品拆分为若干"捆"
        // 每捆的件数依次为 1, 2, 4, 8, ...，最后一捆为余数
        int rest = c; // 剩余待拆分的件数
        for (int bundle = 1; rest > 0; bundle *= 2) {
            // 当前这捆的件数：取 bundle 和剩余件数的较小值
            int cnt = std::min(bundle, rest);
            rest -= cnt;

            // 当前这捆的总体积和总价值
            int bw = cnt * w;
            int bv = cnt * val;

            // 对这一捆做 01 背包（逆序遍历容量）
            for (int j = V; j >= bw; j--) {
                dp[j] = std::max(dp[j], dp[j - bw] + bv);
            }
        }
    }

    std::cout << dp[V] << std::endl;
    return 0;
}

三种背包的代码对比

将 01 背包、完全背包和多重背包的一维 DP 核心代码放在一起，差异一目了然：

// === 01 背包：每种物品最多选 1 件 ===
for (int j = V; j >= w; j--) {                  // 逆序
    dp[j] = max(dp[j], dp[j - w] + val);
}

// === 完全背包：每种物品可选无限件 ===
for (int j = w; j <= V; j++) {                   // 正序
    dp[j] = max(dp[j], dp[j - w] + val);
}

// === 多重背包（朴素）：每种物品最多选 c 件 ===
for (int j = V; j >= w; j--) {                   // 逆序
    for (int k = 1; k <= c && k * w <= j; k++) { // 枚举件数
        dp[j] = max(dp[j], dp[j - k * w] + k * val);
    }
}

规律总结：

• 01 背包：逆序遍历，天然保证每种物品只选 1 次
• 完全背包：正序遍历，天然允许无限次叠加
• 多重背包：逆序遍历（防止叠加）+ 手动枚举件数（精确控制上限）

拓展思考

掌握了 01 背包、完全背包和多重背包这三大基础模型后，可以从以下方向继续深入：

推荐练习

进阶方向

• 混合背包：同一题中可能混合出现 01、完全、多重三种类型的物品，需要根据物品类型选择不同的处理方式
• 分组背包：物品分为若干组，每组至多选一件，外层枚举组、中层逆序遍历容量、内层枚举组内物品
• 二维费用背包：每件物品有两种费用（如体积和重量），需要同时满足两个约束条件