一、课上练习

编程练习

1. 背包问题：L3451

二、知识总结

✨ 核心思想

01背包问题是动态规划中的经典问题，用于解决资源最优分配的问题。

问题定义：

• 给定一个整数 W 表示背包的最大容量
• n 个物品，每个物品 i 有重量 w[i] 和价值 v[i]
• 在不超过背包容量的情况下，选择物品使得总价值最大化

01背包的名称来源于每个物品只能选择一次（选或不选），这是一种二元选择，因此称为"01背包"。

✨ 动态规划解法

状态定义

定义 dp[i][j] 为从前 i 个物品中选出若干物品，使得总重量不超过 j 时的最大总价值。

状态转移方程

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

• 不选择物品 i：dp[i][j] = dp[i-1][j]
• 选择物品 i（前提是 j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]

综合得到状态转移方程：

• 当 j >= w[i] 时：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
• 当 j < w[i] 时：dp[i][j] = dp[i-1][j]

初始化

对所有 j，dp[0][j] = 0，因为没有物品时最大价值为 0。

计算顺序

从左到右、从上到下地填充 dp 表。

最终结果

答案为 dp[n][W]，其中 n 是物品数量，W 是背包的最大容量。

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

✨ 执行示例

以 3 个物品、背包容量 W=5 为例：

物品0: 重量=1, 价值=6
物品1: 重量=2, 价值=10
物品2: 重量=3, 价值=12

dp 表的逐步填充过程：

以 dp[3][5] 为例详解计算过程：

• 不选物品2：dp[2][5] = 16
• 选物品2：dp[2][5-3] + 12 = dp[2][2] + 12 = 10 + 12 = 22
• dp[3][5] = max(16, 22) = 22

最终答案：dp[3][5] = 22，选择物品1（价值10）和物品2（价值12），总重量 2+3=5，总价值 22。

✨ 解题步骤详解

解决 01 背包问题的步骤：

1. 识别问题类型：每个物品只能选或不选（二元选择），有容量限制，求最大价值
2. 整理物品信息：提取每个物品的重量和价值
3. 建立 dp 表：dp[i][j] = 前 i 个物品、容量为 j 时的最大价值
4. 填表：对每个物品 i 和每个容量 j，比较选与不选的价值
5. 读取答案：dp[n][W]

判断 01 背包的特征：

• 有一个"容量"限制（重量、时间、金额等）
• 有若干个"物品"可以选择
• 每个物品有"代价"和"收益"
• 每个物品只能选一次
• 求最大收益

✨ 常见错误

1. 转移方程中 dp[i-1] 写成 dp[i]：01 背包每个物品只能选一次，选物品 i 时应该参考 dp[i-1][j-w[i]]（上一行），写成 dp[i][j-w[i]]（当前行）就变成了完全背包
2. 物品下标和数组下标不对应：dp 数组 i 从 1 开始，但物品数组通常从 0 开始，访问 wt[i-1] 而不是 wt[i]
3. 容量不够时没有特判：当 j < w[i] 时，物品 i 放不下，dp[i][j] 应直接等于 dp[i-1][j]
4. 初始化错误：dp[0][j] 必须全为 0，表示没有物品时价值为 0
5. 求方案数时混淆：如果题目问的是"恰好装满"的方案数而非最大价值，初始化和转移方程都不同

01背包问题的动态规划解法不仅展示了如何利用过去的计算结果来简化未来的计算，还提供了一种思考和解决资源优化问题的框架。

三、课后练习

编程练习

1. 采药：L3452
2. 装箱问题：L3453