一、课上练习

编程练习

1. 完全背包问题：L3461

二、知识总结

✨ 核心思想

完全背包问题与01背包问题类似，但有一个关键的区别：在完全背包问题中，每种物品可以选取无限次。

问题定义：

• 给定一个整数 W 表示背包的最大容量
• n 个物品，每个物品 i 有重量 w[i] 和价值 v[i]
• 每种物品可以选择任意多次，使得背包中的总价值最大，同时不超过背包的容量限制

✨ 动态规划解法

状态定义

dp[i][j] 表示从前 i 种物品中选取若干个（每种可选任意多次），放入容量为 j 的背包中，可以获得的最大价值。

状态转移方程

对于每个物品 i 和每个可能的容量 j：

• 不选物品 i：dp[i][j] = dp[i-1][j]（当 j < w[i] 时）
• 选择物品 i（可多次选择）：dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])（当 j >= w[i] 时）

注意与01背包的区别：选择物品 i 时，使用的是 dp[i][j-w[i]] 而不是 dp[i-1][j-w[i]]，因为同一物品可以被多次选择。

初始化

• 对所有 j，dp[0][j] = 0，因为没有物品时最大价值为 0
• 对所有 i，dp[i][0] = 0，因为容量为 0 时不能装任何物品

一维数组优化

在实际编码中，可以将二维 dp 数组优化为一维数组 dp[j]，表示当前容量为 j 的背包能达到的最大价值。关键在于内层循环从小到大遍历容量，以保证每种物品可以被多次选择。

1#include <iostream>
2#include <vector>
3using namespace std;
4
5int completeKnapsack(int W, const vector<int>& wt, const vector<int>& val) {
6    int n = wt.size();
7    vector<int> dp(W + 1, 0);
8
9    for (int i = 0; i < n; i++) {
10        for (int j = wt[i]; j <= W; j++) {
11            dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
12        }
13    }
14    return dp[W];
15}
16
17int main() {
18    int W = 100;  // Maximum weight of knapsack
19    vector<int> wt = {5, 10, 15};  // Weights of items
20    vector<int> val = {10, 30, 20};  // Values of items
21
22    cout << "Maximum value in knapsack = " << completeKnapsack(W, wt, val) << endl;
23    return 0;
24}

✨ 执行示例

以 3 种物品、背包容量 W=10 为例：

物品0: 重量=5, 价值=10
物品1: 重量=3, 价值=7
物品2: 重量=2, 价值=4

一维 dp 数组的逐步更新（从小到大遍历容量）：

初始： dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

处理物品0（重量5, 价值10）：

dp = [0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 20]

处理物品1（重量3, 价值7）：

dp = [0, 0, 0, 7, 7, 10, 14, 14, 17, 21, 21]

处理物品2（重量2, 价值4）：

• dp[2] = max(0, 4) = 4; dp[4] = max(7, dp[2]+4) = max(7, 8) = 8
• dp[6] = max(14, dp[4]+4) = max(14, 12) = 14（不变）
• ...最终 dp[10] = max(21, dp[8]+4) = max(21, 21) = 21

最终答案：dp[10] = 21，选择 3 个物品1（3x3=9, 3x7=21）。

✨ 解题步骤详解

完全背包与 01 背包的关键区别：

1. 判断问题类型：如果物品可以重复选取，就是完全背包
2. 一维优化的遍历顺序：
   • 01 背包：容量从大到小遍历（保证每个物品只用一次）
   • 完全背包：容量从小到大遍历（允许同一物品被多次选择）
3. 理解为什么遍历顺序不同：从小到大遍历时，dp[j-w[i]] 可能已经在本轮被更新过（已经包含了物品 i），所以物品 i 会被重复选取

✨ 常见错误

1. 遍历顺序搞反：完全背包从小到大，01 背包从大到小，搞反就变成了另一种问题
2. 忘记物品可以无限选取：写状态转移方程时，应该用 dp[i][j-w[i]]（当前行）而不是 dp[i-1][j-w[i]]（上一行）
3. 不理解一维和二维的关系：一维数组优化本质上就是在二维基础上省略了一个维度，遍历顺序是保证正确性的关键
4. 物品为 0 重量的特殊情况：如果存在重量为 0 但价值为正的物品，完全背包会无限循环，需要特判

✨ 01背包与完全背包的对比

三、课后练习

编程练习

1. 数字组合：L3462