当前位置：首页 > backend >正文

ch11题目参考思路

backend 2025/8/12 20:28:36

ch11 题目参考思路

算法 I ch11 - 动态规划：背包问题 I

01 背包计数

知识点：01 背包计数
思路：
- 这一类计数问题与背包问题类似，但物品没有价值属性，只有重量属性 w[i]，要计算有多少种选取物品的方案，使总重量恰好为 m。
- 注意 dp 解决最值问题，是在不同选择中决策取 max 或 min，dp 解决计数问题，是在不同分类中按照计数原理统计。
- dp[i][j] ：前 i 个物品中，取出总重量恰好为 m 的物品选取方案数
  - 实际上还隐含着选取的物品要按照输入的顺序排列，这样才不会将相同物品排列顺序不同的情况重复统计。
- 状态转移：
  - 第一类：不选第 i 个物品，dp[i-1][j]
  - 第二类：要选第 i 个物品（前提是 j >= w[i]），dp[i-1][j-w[i]]
  - 根据加法原理：dp[i][j] = dp[i-1][j] + dp[i-1][j-w[i]]
- 边界：
  - 0 个物品里选出重量为 0，有“啥都不选”这一种方案，dp[0][0] = 1
  - 0 个物品里选出重量 > 0，不可能选出来，dp[0][1~m] = 0
- 写对二维的写法后，尝试用滚动数组优化。

Money

知识点：完全背包计数
思路：
- 本题将货币看作物品，货币面值看作物品重量，转换为背包模型。
- 与 01 背包计数类似，区别是同一类物品可以取任意次，在加入一个第 i 类物品之前，背包里也可以有第 i 类物品，只需要将状态转移方程改为 dp[i][j] = dp[i-1][j] + dp[i][j-w[i]] 。
代码：
- 根据思路和前面题目的代码思考尝试。写对二维的写法后，尝试用滚动数组优化。

购物规划

知识点：01 背包的应用
思路：
- 将两类商品分开处理比较方便，先处理第一类的物品，再处理第二类包包。
- 第一类物品的处理与 01 背包相同，只是不能将容量限制为初始容量 m，因为后面还可能扩容，要按照扩容后的最大容量计算，计算出每个 dp[i][j] 的值。
- 第二类包包计算扩展到容量 j 的最小代价 dp2[i][j]。
- 最后枚举每个容量 j，对（第一类获取的价值 - 第二类花费的价值）打擂台求最大值。

代码：

#include <bits/stdc++.h>
using namespace std;const int maxn = 1010, maxm = 100010 * 2;
using ll = long long;
// f1[i][j] 的一维优化: 前 i 件物品，容量为 j 的包能装的最大价值
// f2[i][j] 的一维优化: 前 i 件包包，买到容量为 j 的包能花的最小价钱
ll f1[maxm], f2[maxm];
int n, W, w[maxn], v[maxn], op[maxn];
int main() {memset(f2, 0x3f, sizeof(f2));cin >> n >> W;for (int i = 0; i <= W; ++i) f2[i] = 0;for (int i = 1; i <= n; ++i) {cin >> op[i] >> w[i] >> v[i];}W += 1000 * 100;for (int i = 1; i <= n; ++i) {if (op[i] == 1)continue;for (int j = W; j >= w[i]; --j) {f2[j] = min(f2[j], f2[j - w[i]] + v[i]);}}for (int i = 1; i <= n; ++i) {if (op[i] == 2)continue;for (int j = W; j >= w[i]; --j) {f1[j] = max(f1[j], f1[j - w[i]] + v[i]);}}ll res = 0;// 枚举所有的背包容量，寻找最大能赚取的价值for (int j = 0; j <= W; ++j) {res = max(res, f1[j] - f2[j]);}cout << res;return 0;
}

巨型背包

知识点：01 背包、换维
思路：
- 本题也是 01 背包问题，只是数据范围比较特殊。如果按照之前的状态设计，第二维表示重量限制，开不了那么大的数组。
- 需要进行“换维”，比较小的价值作为 dp 数组下标，大的重量作为 dp 数组的值。（这启示我们不一定题目怎么问就怎么设计 dp 状态，多角度考虑，换个状态表示也许能让复杂度更优）
- dp[i][j]：前 i 个物品选出总价值为 j 时的最小总重量
  - 注意第二维表示价值，第二层 for 循环要根据最大总价值是多少来确定循环到多少。
- 状态转移：
  - 不选第 i 个物品，dp[i-1][j]
  - 要选第 i 个物品（前提 j >= v[i]），dp[i-1][j-v[i]] + w[i]
  - 要最小总重量，所以在两种选择中取 min
- 边界：
  - dp[0][0] = 0
  - 0 个物品不可能选出 > 0 的价值，用无穷大值 INF 来表示，dp[0][1~V] = INF。其中 V 表示最大总价值。
- 结果：满足 dp[n][j] <= m 的最大的 j
代码：
- 根据 01 背包的代码和本题思路思考尝试。

装箱问题

知识点：数字拼凑的判断
思路：
- 本题与背包计数问题类似，都是给出物品的重量或体积，没有价值。本题希望在容量 V 的限制下，选择物品拼凑出尽量大的体积。只要方案数 > 0，就说明能拼凑出来，可以根据背包计数的 dp[n][i] > 0 是否成立来判断总体积能否恰好达到 i。
  - 但这样有个问题，方案数计算结果可能很大，溢出数据范围，如果正确值 > 0，溢出后的错误值恰好 == 0，那么就会出错。
- 只关心可以达到（true）和不能达到（false），用 bool 数组即可。
- dp[i][j]：前 i 个物品中，能否选一些物品拼凑出恰好为 j 的总体积。
- 状态转移
  - dp[i][j] = dp[i-1][j] | dp[i-1][j-w[i]] （这里的 | 是位运算中的“或”，用逻辑运算的 || 也可以）
  - 意思是如果“前 i - 1 个物品能拼凑出总体积 j”，那么前 i 个物品能拼凑出总体积 j。
  - 或者如果“前 i - 1 个物品能拼凑出总体积 j - w[i]”，那么选第 i 个物品加入，也就能拼凑出总体积 j 。
  - 思考如果是完全背包（每个物品能取无限次），状态转移如何修改。
- 边界：
  - 0 个物品里选出重量为 0，“啥都不选”就能达到，dp[0][0] = true
  - 0 个物品里选出重量 > 0，无法达到，dp[0][1~m] = false
- 结果：找到满足 dp[n][j] == true 的最大的 j，答案是 V - j 。
- 本题有多种做法，例如比较直观的想法是用 dp[i][j] 表示前 i 个物品中，选出总体积不超过 j 的物品的最小剩余容量。
代码：
- 根据本题思路思考尝试。写对二维的写法后，尝试用滚动数组优化。