B2174 完全背包

GESP C++六级练习。完全背包DP模板题，是学习动态规划背包系列的入门必刷题。本题直接对应完全背包的标准模型，适合初次接触背包DP的同学理解状态定义、转移方程以及正序遍历的含义。难度⭐⭐。洛谷难度等级普及-。

B2174 完全背包

题目要求

题目描述

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

每种物品都有无限件，你可以选择任意多件放入背包，但总容量不能超过 $V$。

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

形式化题意：设第 $i$ 种物品选择 $x_i$ 件（$x_i$ 为非负整数），则需要满足：

$$\sum_{i=1}^{n} x_i \cdot w_i \le V,\quad x_i \ge 0$$

最大化目标：

$$\max \sum_{i=1}^{n} x_i \cdot val_i$$

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

3 10
2 3
3 4
4 5

输出 #1

15

说明/提示

样例说明 #1

一种最优方案是选择第 1 种物品 $5$ 件：

• 总体积 $5 \times 2 = 10 \le 10$
• 总价值 $5 \times 3 = 15$

数据范围

对于 $40\%$ 的数据，$1\le n \le 8$，$1\le V \le 12$，且对所有 $i$，$1\le w_i \le 1000$，$0\le val_i \le 1000$。

对于 $100\%$ 的数据，$1\le n \le 1000$，$1\le V \le 1000$，且对所有 $i$，$1\le w_i \le 1000$，$0\le val_i \le 1000$。

题目分析

本题是完全背包问题的标准模板题。如果你已经理解了 01 背包或者刚做完六级真题中的「条形蛋糕」（P17012），那么本题可以帮助你进一步巩固完全背包的模型——事实上，条形蛋糕本质上就是一个完全背包问题的等价建模。

1. 01 背包 vs 完全背包：区别在哪？

在 01 背包 中，每种物品只有 1 件，选了就没了；在 完全背包 中，每种物品有无限件，同一种物品可以反复选取。

两者的状态定义完全一样，但转移时的遍历顺序不同：

仅仅是内层循环方向的一字之差，就从"每种物品最多选一件"变成了"每种物品可选无限件"。下文会详细解释其中的原理。

2. 状态定义

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

初始状态：$dp[0] = 0$，其余全为 $0$（表示什么都不装时价值为 $0$）。

3. 状态转移方程

对于第 $i$ 种物品（体积 $w_i$，价值 $val_i$），对每个容量 $j$（$w_i \le j \le V$）：

方程含义：面对容量 $j$，我们有两种选择：

1. 不选第 $i$ 种物品：价值保持 $dp[j]$ 不变
2. 选一件第 $i$ 种物品：腾出 $w_i$ 的空间后，剩余容量 $j - w_i$ 的最大价值为 $dp[j - w_i]$，加上本件价值 $val_i$

取两者的最大值。

4. 从二维到一维——如何理解一维 $dp[j]$ 的含义？

如果你觉得二维 $dp[i][j]$ 很直观，但一维 $dp[j]$ 突然就看不懂了，那是因为这中间缺了一个推导过程。

二维 DP 的完整图景

二维数组 $dp[i][j]$ 是一张 $(n+1) \times (V+1)$ 的表格。外层循环从第 $1$ 行填到第 $n$ 行，每一行代表"考虑前 $i$ 种物品时各容量的最优解"。

关键观察：填第 $i$ 行时，只需要读第 $i-1$ 行的数据（对于 01 背包）或第 $i-1$ 行和第 $i$ 行已填好的部分（对于完全背包）。更早的第 $1, 2, \ldots, i-2$ 行在填第 $i$ 行时已经完全用不到了。

既然旧行用不到，那就不存了

这就像考试交卷——交完上一科的试卷就可以丢掉草稿纸了，下一科重新用同一张纸。

我们只保留一行，让这一行在外层循环的每一轮中被"原地覆盖更新"：

• 外层循环开始处理第 $1$ 种物品之前：$dp[j]$ 全为 $0$，等价于 $dp[0][j]$（不考虑任何物品）
• 处理完第 $1$ 种物品之后：$dp[j]$ 被覆盖为 $dp[1][j]$（只考虑前 $1$ 种物品的最优解）
• 处理完第 $2$ 种物品之后：$dp[j]$ 被覆盖为 $dp[2][j]$（只考虑前 $2$ 种物品的最优解）
• ……
• 处理完第 $n$ 种物品之后：$dp[j]$ 被覆盖为 $dp[n][j]$（考虑全部 $n$ 种物品的最优解）

一维 $dp[j]$ 的真正含义

所以，一维 $dp[j]$ 并不是一个"固定含义"的状态——它的含义随着外层循环的推进而变化：

在外层循环处理完前 $k$ 种物品之后，$dp[j]$ 的含义等价于 $dp[k][j]$，即"只考虑前 $k$ 种物品、背包容量为 $j$ 时的最大总价值"。

当整个外层循环结束时（$k = n$），$dp[V]$ 就等价于 $dp[n][V]$，即最终答案。

理解了这一点之后，下面讨论的"正序/逆序遍历"就容易理解了——它解决的是：在覆盖更新的过程中，如何保证读到的是正确的值？

5. 正序 vs 逆序遍历——一个方向的差别，为什么结果完全不同？

这是理解背包 DP 的最核心要点。

从二维 DP 的转移方程说起

要理解一维 DP 中遍历方向的逻辑，最好的切入点是先回到二维 DP 的转移方程，看看 01 背包和完全背包在逻辑上到底有什么不同。

01 背包的二维转移方程：

完全背包的二维转移方程：

唯一的区别在于"选一件"时查找剩余容量的最优值用的是哪一行：

• 01 背包用 $dp[i-1][j - w_i]$：剩余容量 $j - w_i$ 的最优方案不包含物品 $i$ → 我选的这一件就是唯一的一件
• 完全背包用 $dp[i][j - w_i]$：剩余容量 $j - w_i$ 的最优方案可能已经包含了若干件物品 $i$ → 我在已有的基础上再加一件，自然就实现了无限选取

这就是两种背包在算法逻辑上的本质区别。

一维压缩时，遍历方向如何实现这个逻辑？

当我们把二维数组压缩成一维时，$dp[j]$ 在不同时刻代表不同含义：

• 更新前：$dp[j]$ 保存的是"上一轮"的值，即 $dp[i-1][j]$
• 更新后：$dp[j]$ 被覆盖为"本轮"的值，即 $dp[i][j]$

因此，问题变成了：当我们计算 $dp[j]$ 时，$dp[j - w]$ 处于"更新前"还是"更新后"？

• 逆序遍历（从大到小）：$j$ 从大到小处理，而 $j - w < j$，所以 $dp[j - w]$ 还没轮到更新，保存的仍是上一轮的值 $dp[i-1][j-w]$ → 对应 01 背包的转移方程
• 正序遍历（从小到大）：$j$ 从小到大处理，而 $j - w < j$，所以 $dp[j - w]$ 已经被更新过，保存的是本轮的值 $dp[i][j-w]$ → 对应完全背包的转移方程

总结：遍历方向决定了 $dp[j - w]$ 读到的是"旧行"还是"新行"的数据，从而精确地实现了两种背包各自的转移逻辑。

一句话概括：逆序遍历让 $dp[j-w]$ 保持为 $dp[i-1][j-w]$（不含物品 $i$）→ 最多选一次；正序遍历让 $dp[j-w]$ 变为 $dp[i][j-w]$（可能已含物品 $i$）→ 允许无限选取。

用同一组数据验证

理解了上面的逻辑后，我们用具体数据来验证。假设只有一种物品：体积 $w = 2$，价值 $val = 3$，背包容量 $V = 6$。初始 $dp$ 数组全为 $0$。

正序遍历（完全背包）—— $j$ 从 $2$ 到 $6$：

$dp[j - 2]$ 读到的是本轮新值（即 $dp[i][j-2]$），所以每一步都"站在前一步的肩膀上"，物品被不断叠加。

逆序遍历（01 背包）—— $j$ 从 $6$ 到 $2$：

$dp[j - 2]$ 读到的是上轮旧值（即 $dp[i-1][j-2]$），每一步的决策互不干扰，物品最多只被选了 $1$ 次。

5. 与「条形蛋糕」（P17012）的关联

六级真题「条形蛋糕」（P17012）的转移方程为：

如果我们把蛋糕总长度 $n$ 视为背包容量，长度为 $j$ 的蛋糕块视为一种物品（体积 $= j$，价值 $= p_j$），每种物品可以无限使用，那么条形蛋糕就是一个完全背包问题。两道题的代码结构几乎相同，理解了一道就能理解另一道。

6. 样例验证

以样例为例（$n = 3, V = 10$）：

物品 $1$ 的性价比最高。选 $5$ 件物品 $1$：总体积 $= 5 \times 2 = 10$，总价值 $= 5 \times 3 = 15$。

DP 数组的完整更新过程（仅展示处理完所有物品后的最终结果）：

最终 $dp[10] = 15$，与样例输出一致。

注意：虽然本例中性价比最高的贪心策略恰好得到了正确答案，但贪心策略并非对所有背包问题都成立。动态规划才能保证找到全局最优解。

7. 复杂度分析

• 时间复杂度：$O(n \times V)$，外层循环 $n$ 种物品，内层循环容量 $V$
• 空间复杂度：$O(V)$，一维滚动数组

在本题数据范围下（$n, V \le 1000$），运算次数约为 $10^6$，远在时间限制内。

8. 注意事项

• $dp$ 数组初始化为全 $0$ 即可，因为我们求的是"不超过容量 $V$“的最大价值，空背包价值自然为 $0$
• 内层循环起点为 $w_i$（而非 $0$），因为容量小于 $w_i$ 时无法放入该物品，无需更新
• 最大总价值不会超过 $n \times \max(val_i) \times \lfloor V / \min(w_i) \rfloor$，在本题数据范围下 int 类型足以存储

示例代码

通过一维 DP 数组正序遍历求解完全背包的最大价值。

#include <iostream>

// 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;
        std::cin >> w >> val;

        // 内层循环：正序遍历容量（完全背包的关键）
        // 从 w 开始，因为容量小于 w 时无法放入该物品
        for (int j = w; j <= V; j++) {
            // 状态转移：选或不选第 i 种物品（可以重复选）
            // dp[j - w] 可能已经包含了本轮选过的物品 i，从而实现无限选取
            if (dp[j - w] + val > dp[j]) {
                dp[j] = dp[j - w] + val;
            }
        }
    }

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

二维数组解法（更直观）

上面的一维滚动数组写法虽然简洁高效，但对初学者来说不太容易理解"正序遍历为什么能实现重复选取”。下面给出二维数组的写法，用 $dp[i][j]$ 明确表示"前 $i$ 种物品、背包容量为 $j$ 时的最大总价值"，状态含义一目了然。

#include <iostream>

// dp[i][j] 表示：前 i 种物品、背包容量为 j 时的最大总价值
int dp[1005][1005];
int w[1005], val[1005];

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

    for (int i = 1; i <= n; i++) {
        std::cin >> w[i] >> val[i];
    }

    // 外层循环：枚举前 i 种物品
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            // 不选第 i 种物品：继承前 i-1 种物品的结果
            dp[i][j] = dp[i - 1][j];
            // 选（至少）一件第 i 种物品
            // 注意这里是 dp[i][j - w[i]]，而不是 dp[i-1][j - w[i]]
            // 用的是"本行"已更新的值，所以同一物品可以被反复选取
            if (j >= w[i] && dp[i][j - w[i]] + val[i] > dp[i][j]) {
                dp[i][j] = dp[i][j - w[i]] + val[i];
            }
        }
    }

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

二维写法的核心理解点：转移时用的是 dp[i][j - w[i]]（本行已更新的值），而非 dp[i-1][j - w[i]]（上一行的旧值）。如果把 dp[i] 改成 dp[i-1]，就变成了 01 背包。通过下标就能直观看出两种背包的本质区别。

小提示：二维写法空间开销较大（$O(n \times V)$），在本题数据范围下（$n, V \le 1000$）约需 $4$ MB，仍可通过。但在数据范围更大的题目中，建议使用一维滚动数组优化空间。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号