DP：背包问题

mydcwfy · 2021-08-03 17:05:53 · 个人记录

背包问题

0. 前言

这一章虽然比较简单，但是非常的重要，包含 DP 的基本思想。

我也会尽可能地清楚讲解。

1. 基本思想

所有的 DP 问题几乎可以转化为“集合的表示和转移”。

不同的集合是由不同的状态所区分。

例如 01 背包问题，f[i,j] 表示从前 i 个物品中选，且总花费不超过 j 的所有取法的集合。

然后，这个集合有一个代表元素，表示所有取法的某种属性。

如 01 背包，f[i,j] 表示所有取法的最大值。

集合处理好之后，我们考虑如何集合转移。

当前集合一般会根据最后一步的决策来划分。

再如 01 背包，根据是否选择 i 物品来划分。

选择 i 物品，即为 f[i-1,j-v[i]]，再加上 w[i] 的价值。

不选择 i 物品，即为 f[i-1,j]。

以上就是背包问题乃至 DP 所有问题的核心，我们再一次梳理一下：

1. 考虑集合的构建和集合的属性。
2. 考虑集合的划分以及集合属性的计算。
3. 考虑细节（边界问题，答案输出等）

2. 背包问题

1）01 背包

题目大致为：从 n 个物品中选，每一个物品有体积 v[i] 和价值 w[i]，每个物品只能选一次，求总体积不超过 m 的最大价值。

前面已经讲到，用 f[i,j] 表示从前 i 个物品中选，总体积不超过 j 的所有取法。

属性为最大值，及所有取法价值的最大。

考虑转移。

如果选 i 物品，即为 f[i-1,j-v[i]]+w[i]。

如果不选，即为 f[i-1,j]。

两种情况取最大值即可。

2）完全背包

题目大致为：还是有 n 个物品，有体积 v 和价值 w，每个物品可以取无限次，有总体积不超过 m 的最大价值。

假设体积 j 最多能放 s 个 v[i] 的物品。

那么，还是向上面一样的定义方式，我们考虑怎么转移。

我们可以取 0,1,..,s-1,s 个 i 物品。

那么，f[i][j]=\max(f[i-1,j-k\times v[i]]+k\times w[i])，其中 0\leq k\leq s。

3）多重背包

和前面差距不大，只是每个物品最多取 s[i] 个。

如果不优化的话，几乎和上面一样。