01 背包
题目描述
有 $n$ 个物品，一个体积为 $V$ 的背包。
第 $i$ 个物品体积为 $v_i$，价值为 $w_i$。
每个物品只能选择一次，最大化放入背包物品的总价值。
输出最大总价值。
状态表示
集合
令 $f_{i,j}$ 表示 从前 $i$ 个物品中选，总体积不超过 $j$ 的方案集合。
属性
集合中的 最大价值。
状态转移
故
$$
f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-v_i}+w_i\}
$$
DP 时间复杂度为 $O(nV)$。
初始条件
当选择 $0$ 个物品时，无论总体积为多少，总价值都是 $0$，故
$$
f_{0,j}=0\,(j\in[0,V])
$$
最终结果
最终应当是 从前 $n$ 个物品中选，总体积不超过 $V$ 的方案中的最大价值，即
$$
f_{n,V}
$$
代码实现
1 |
|
完全背包
题目描述
有 $n$ 个物品，一个体积为 $V$ 的背包。
第 $i$ 个物品体积为 $v_i$，价值为 $w_i$。
每个物品可以选择无限次，最大化放入背包物品的总价值。
输出最大总价值。
状态表示
集合
令 $f_{i,j}$ 表示 从前 $i$ 个物品中选，总体积不超过 $j$ 的方案集合。
属性
集合中的 最大价值。
状态转移
$$
f_{i,j}=\max\limits_{k=0}^{\big\lfloor\frac{j}{v_i}\big\rfloor}\{f_{i-1,j-kv_i}+kw_i\}
$$
这样 DP 的时间复杂度是 $O(nV^2)$ 的，有没有优化方法呢？
可以发现
$$
\begin{aligned}
f_{i,j}&=\max\{f_{i-1,j},f_{i-1,j-v_i}+w_i,f_{i-1,j-2v_i}+2w_i,f_{i-1,j-3v_i}+3w_i,\cdots\}\\
f_{i,j-v_i}&=\max\{\hspace{1.3 cm}f_{i-1,j-v_i},\hspace{1.1 cm}f_{i-1,j-2v_i}+w_i,\hspace{0.27 cm}f_{i-1,j-3v_i}+2w_i,\cdots\}
\end{aligned}
$$
故
$$
f_{i,j}=\max\{f_{i,j-v_i}+w_i,f_{i-1,j}\}
$$
此时时间复杂度降为 $O(nV)$。
初始条件
当选择 $0$ 个物品时，无论总体积为多少，总价值都是 $0$，故
$$
f_{0,j}=0\,(j\in[0,V])
$$
最终结果
最终应当是 从前 $n$ 个物品中选，总体积不超过 $V$ 的方案中的最大价值，即
$$
f_{n,V}
$$
代码实现
1 |
|
多重背包
题目描述
朴素算法
状态表示
有 $n$ 种物品，一个体积为 $V$ 的背包。
第 $i$ 个物品体积为 $v_i$，价值为 $w_i$。
每个物品可以选择 $s_i$ 次，最大化放入背包物品的总价值。
输出最大总价值。
集合
令 $f_{i,j}$ 表示 从前 $i$ 种物品中选，总体积不超过 $j$ 的方案集合。
属性
集合中的 最大价值。
状态转移
故
$$
f_{i,j}=\max\limits_{k=0}^{\min\{s_i,\frac{j}{v_i}\}}\{f_{i-1,j-kv_i}+kw_i\}
$$
初始条件
当选择 $0$ 个物品时，无论总体积为多少，总价值都是 $0$，故
$$
f_{0,j}=0\,(j\in[0,V])
$$
最终结果
最终应当是 从前 $n$ 种物品中选，总体积不超过 $V$ 的方案中的最大价值，即
$$
f_{n,V}
$$
代码实现
1 |
|
二进制优化
引理：
$\forall\,n\in\mathbb{N^{*}}$，$n$ 可以分解为 $2^0,2^1,\cdots,2^k,s(2^0+2^1+\cdots+2^k+s=n,s\in[0,2^{k+1})$。这些数可以凑出 $1\sim n$ 中的任何正整数。
证明：
显然地，$2^0,2^1,\cdots,2^k$ 可以凑出 $[1,2^{k+1}-1]$ 之间的所有正整数。
将其中每个数 $+s$，则可以凑出 $[s,n]$ 之间的所有正整数。
因为 $s\le2^{k+1}-1$，所以 $[1,2^{k+1}-1],[s,n]$ 必然能覆盖 $[1,n]$ 中的所有正整数。
证毕。
对于每种物品的个数 $s$，我们也可以按照这样的方法拆分，做 01 背包。
代码实现
1 |
|
单调队列优化
在朴素算法中，状态转移方程如下：
$$
f_{j}\gets\max\{f_j,f_{j-v}+w,f_{j-2v}+2w,f_{j-3v}+3w,\cdots,f_{j-sv}+sw\}(假设\,j\ge sv)
$$
容易发现，$\{f_j,f_{j-v},f_{j-2v},\cdots,f_{j-sv}\}\sub\bar{j}(\bmod v)$，即这些数同属一个模 $m$ 的同余系。
不同同余系之间不相干，所以我们可以在一个同余系内考虑。
可以发现，求 $f_j$ 其实就是求一段长度为 $s$ 的区间的最大值，故考虑使用单调队列。
令非负整数 $q\in[0,v)$，可得如下式子：
$$
\begin{aligned}
f_{q}&=\max\{f_{q}\}\\
f_{q+v}&=\max\{f_{q+v},f_{q}+w\}\\
f_{q+2v}&=\max\{f_{q+2v},f_{q+v}+w,f_{q}+2w\}\\
&\hspace{3 cm}\vdots\\
f_{q+pv}&=\max\{f_{q+pv},f_{q+(p-1)v}+w,f_{q+(p-2)v}+2w,\cdots,f_{q}+pw\}
\end{aligned}
$$
上面的最后一个式子只是理想情况，可能取不到 $f_q$。
可以发现在第 $1$ 个式子中是 $f_q$，第 $2$ 个式子中是 $f_q+w$，最后一个式子中为 $f_q+pw$。队列中的值都在变化，是无法使用单调队列的。
怎么办呢？
其实可以把 $\max$ 中的 $w$ 都提出来，得到如下式子：
$$
\begin{aligned}
f_{q}&=\max\{f_{q}\}\\
f_{q+v}&=\max\{f_{q+v}-w,f_{q}\}+w\\
f_{q+2v}&=\max\{f_{q+2v}-2w,f_{q+v}-w,f_{q}\}+2w\\
&\hspace{5 cm}\vdots\\
f_{q+pv}&=\max\{f_{q+pv}-pw,f_{q+(p-1)v}-(p-1)w,f_{q+(p-2)v}-(p-2)w,\cdots,f_{q}\}+pw
\end{aligned}
$$
此时队列中原有的元素就不会发生变化了。
虽然在单调队列中插入的只是下标（如 $q,q+v,\cdots,q+pv$），但是这个下标 $r$ 所代表的值 $\operatorname{val}(r)$ 为多少呢？
假设 $r=m+nv$。
通过观察可以发现，$w$ 的系数就是 $n$，故：
$$
\operatorname{val}(r)=f_{r}-\dfrac{r-m}{v}w
$$
有了 $\operatorname{val}(r)$，就可以解决当前元素插入单调队列队尾的问题了。
然后我们要解决如何判断队头是否过时的问题。
假设当前队头 $a=j+xv$，当前的体积 $b=j+yv(x 容易发现，当 $y-x>s$ 时，队头就失效了。 又因为 $b-a=(y-x)v$，所以队头失效的条件为： 最后，我们应该知道如何用单调队列队头 $a$ 来更新 $f_b$。 朴素式子中第 $2$ 项以以后的元素都是在单调队列中的，所以后面这些值的 $\max$ 相当于 $\operatorname{val}(a)$。 因为 $b=j+yv$，所以 $\max$ 外的 $w$ 的系数为 $y=\dfrac{b-j}{v}$。 故可得： 该算法时间复杂度为 $O(nV)$。 PS：具体实现时，如果只开一个一维数组，那么就应当倒序循环。但是如果倒序循环，单调队列就无法优化。所以应该采用滚动数组技巧。此处使用 $f$ 存储这一层，$g$ 存储上一层。 有 $n$ 种物品，一个体积为 $V$ 的背包。 物品一共有三类： 第 $i$ 种物品，体积为 $v_i$，价值为 $w_i$。 最大化放入背包物品的总价值，并输出最大总价值。 01 背包、完全背包、多重背包的混合版。 可以分类讨论： 有 $n$ 组物品，一个体积为 $V$ 的背包。 第 $i$ 组物品有 $s_i$ 个，同一组内的物品最多只能选一个。 第 $i$ 组内的第 $j$ 个物品，体积为 $v_{i,j}$，价值为 $w_{i,j}$。 最大化放入背包物品的总价值，并输出最大总价值。 令 $f_{i,j}$ 表示 从前 $i$ 组物品中选，总体积不超过 $j$ 的方案集合。 集合中的 最大价值。 故 当从前 $0$ 组物品中选择时，无论总体积为多少，总价值都是 $0$，故 最终应当是 从前 $n$ 组物品中选，总体积不超过 $V$ 的方案中的最大价值，即 有 $n$ 组物品，一个体积为 $V$，最大承重为 $M$ 的背包。 第 $i$ 个物品体积为 $v_i$，重量为 $m_i$，价值为 $w_i$。 令 $f_{i,j,k}$ 表示 从前 $i$ 个物品中选，总体积不超过 $j$，总重量不超过 $k$ 的方案集合。 集合中的 最大价值。 与 01 背包类似，分选择和不选两种情况。 故 当选择 $0$ 个物品时，无论总体积、总重量为多少，总价值都是 $0$，故 最终应当是 从前 $n$ 个物品中选，总体积不超过 $V$，总重量不超过 $M$ 的方案中的最大价值，即 有 $n$ 个物品和一个体积为 $V$ 的背包。 物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。 第 $i$ 个物品体积为 $v_i$，价值为 $w_i$，依赖的父结点编号为 $p_i$。若 $p_i=-1$，则表示根节点。 求解将哪些物品装入背包，可使物品总体积不超过背包体积，且总价值最大。 输出最大价值。 令 $f_{u,j}$ 表示 在以 $u$ 为根结点的子树中（包含 $u$），总体积不超过 $j$ 的方案集合。 集合中的 最大价值。 对于每个儿子，可以用体积划分集合。 由于每个儿子只能有一种体积，所以相当于一个分组背包。 $$
f_{u,j}=0\,(j\in[1,n],j\in[1,V])
$$ 最终结果应为在根结点的子树中，总体积不超过 $V$ 的方案集合，即 有 $n$ 件物品，体积为 $V$ 的背包。 第 $i$ 件物品体积为 $v_i$，价值为 $w_i$，每件物品只能用一次。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包体积，且总价值最大。 输出 最优选法的方案数。注意答案可能很大，请输出答案模 $10^9+7$ 的结果。 令 $f_{i,j}$ 表示从前 $i$ 个物品中选，总体积 恰好 为 $j$ 的方案集合。 集合中的 最大价值。 令 $g_{i,j}$ 表示到达 $f_{i,j}$ 的方案数。 可以知道， 由于 $f_{i,j}$ 表示 恰好 总体积为 $j$ 的方案集合，那么 令 $k$ 表示背包中的最大总价值，即 $f$ 中的最大值。此时答案为： 有 $n$ 件物品和一个体积为 $V$ 的背包。 第 $i$ 件物品体积为 $v_i$，价值为 $w_i$，每件物品只能用一次。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包体积，且总价值最大。 输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。 令 $f_{i,j}$ 表示从后 $n-i+1$ 件物品中选，总体积不超过 $j$ 的方案集合（至于为什么要这样，见下文）。 集合中的最大价值。 容易知道， $$
f_{n+1,j}=0\,(j\in[0,V])
$$ 题目要求输出 字典序最小的方案。从前往后考虑，每个物品必然是 能选就选。 如何知道第 $i$ 个物品能不能选呢？ 可以看 $f_{i,j}$ 是否从选第 $i$ 个物品的情况转移过来（如果 $f_{i+1,j}=f_{i+1,j-v_i}+w_i$，根据能选就选的原则，也得选） Q：为什么要这样定义 $f_{i,j}$？ A：倒着定义，$f_{1,V}$ 就是全局最优解。根据转移的情况来向后推，$f_{2,\Delta V},f_{2,\Delta V'},\cdots$ 都是全局最优解，保证输出结果是全局最优方案。但是如果正着定义，$f_{1,V}$ 是局部最优解，在后面的转移中可能没有入选，会导致输出结果不是全局最优方案。 可以发现输出 2 只是纯粹的能选就选，没有考虑全局情况。 （这里可能解释不清楚，轻喷/kk） 详见代码。 令 $f_{j}$ 表示体积能否凑到 $j$。 假设当前枚举到第 $i$ 个位置，则
$$
\boxed{b-a>sv}
$$
$$
\begin{aligned}
f_b&=\max\left\{f_b-\dfrac{b-j}{v}w,\operatorname{val}(a)\right\}+\dfrac{b-j}{v}w\\
&=\max\left\{f_b-\dfrac{b-j}{v}w+\dfrac{b-j}{v}w,f_a-\dfrac{a-j}{v}w+\dfrac{b-j}{v}w\right\}\\
&=\max\left\{f_b,f_a+\dfrac{b-a}{v}w\right\}
\end{aligned}
$$
此时就可以 $O(1)$ 计算 $f_b$ 了。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N = 2e4 + 10;
int n, V, f[N], g[N], q[N]; // f,g 为 DP 数组，q 为单调队列（最大容量为 V）
int main() {
std::cin >> n >> V;
for (int i = 1, v, w, s; i <= n; ++i) {
std::cin >> v >> w >> s;
memcpy(g, f, sizeof(f)); // g <- f
for (int j = 0; j < v; ++j) { // 枚举同余类
int hh = 0, tt = -1; // 单调队列的头和尾
for (int k = j; k <= V; k += v) { // 在同一个同余类内枚举体积
while (hh <= tt && k - q[hh] > s * v) ++hh; // 弹出队头
if (hh <= tt) f[k] = std::max(g[k], g[q[hh]] + (k - q[hh]) / v * w); // 状态转移
while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) --tt; // 弹出队尾
q[++tt] = k; // 插入当前元素
}
}
}
std::cout << f[V] << std::endl;
return 0;
}混合背包
题目描述
解决方法
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int N = 1e3 + 10;
int n, V, f[N];
int main() {
std::cin >> n >> V;
for (int i = 1, v, w, s; i <= n; ++i) {
std::cin >> v >> w >> s; // 本题中 s=-1 为第一类，s=0 为第二类，s 是正整数为第三类
if (!s) { // 完全背包
for (int j = v; j <= V; ++j)
f[j] = std::max(f[j], f[j - v] + w);
} else {
if (s == -1) s = 1; // 01 背包->多重背包
for (int k = 1; k <= s; k <<= 1) {
for (int j = V; j >= k * v; --j)
f[j] = std::max(f[j], f[j - k * v] + k * w);
s -= k;
}
if (s)
for (int j = V; j >= s * v; --j)
f[j] = std::max(f[j], f[j - s * v] + s * w);
}
}
std::cout << f[V] << std::endl;
return 0;
}分组背包
题目描述
状态表示
集合
属性
状态转移
$$
f_{i,j}=\max\{f_{i-1,j},\max\limits_{k=1}^{s_i}\{f_{i-1,j-v_{i,k}}+w_{i,k}\}\}
$$初始条件
$$
f_{0,j}=0\,(j\in[0,V])
$$最终结果
$$
f_{n,V}
$$代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 110; // 假设 V,s[i] 同阶
int n, V, v[N], w[N], f[N];
int main() {
std::cin >> n >> V;
for (int i = 1, s; i <= n; ++i) {
std::cin >> s;
for (int j = 1; j <= s; ++j) std::cin >> v[j] >> w[j];
for (int j = V; ~j; --j)
for (int k = 1; k <= s; ++k)
if (j >= v[k]) f[j] = std::max(f[j], f[j - v[k]] + w[k]);
}
std::cout << f[V] << std::endl;
return 0;
}二维费用背包
题目描述
每个物品只能选择一次，最大化放入背包物品的总价值。
输出最大总价值。状态表示
集合
属性
状态转移
$$
f_{i,j,k}=\max\{f_{i-1,j,k},f_{i-1,j-v_i,k-m_i}+w_i\}
$$初始条件
$$
f_{0,j,k}=0\,(j\in[0,V],k\in[0,M])
$$最终结果
$$
f_{n,V,M}
$$代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 1e2 + 10;
int n, V, M, f[N][N];
int main() {
std::cin >> n >> V >> M;
for (int i = 1, v, m, w; i <= n; ++i) {
std::cin >> v >> m >> w;
for (int j = V; j >= v; --j)
for (int k = M; k >= m; --k)
f[j][k] = std::max(f[j][k], f[j - v][k - m] + w);
}
std::cout << f[V][M] << std::endl;
return 0;
}有依赖的背包问题
题目描述
状态表示
集合
属性
状态转移
初始条件
最终结果
$$
f_{\text{root},V}
$$
$\text{root}$ 为树的根结点。代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int N = 110;
std::vector<int> g[N];
int n, V, root, v[N], w[N], f[N][N];
void dp(int u) {
for (auto son : g[u]) { // 遍历儿子
dp(son);
for (int j = V - v[u]; ~j; --j) // 由于一定要包含 u 结点，所以最大体积为 V-v[u]
for (int k = 0; k <= j; ++k)
f[u][j] = std::max(f[u][j], f[u][j - k] + f[son][k]);
}
for (int i = V; i >= v[u]; --i) f[u][i] = f[u][i - v[u]] + w[u]; // 加入 u，更新
for (int i = 0; i < v[u]; ++i) f[u][i] = 0; // 不可能的情况
}
int main() {
std::cin >> n >> V;
for (int i = 1, p; i <= n; ++i) {
std::cin >> v[i] >> w[i] >> p;
if (p == -1) root = i;
else g[p].push_back(i);
}
dp(root);
std::cout << f[root][V] << std::endl;
return 0;
}背包问题求方案数
题目描述
状态表示
集合
属性
状态转移
$$
f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-v_i}+w_i\}
$$
可以分三类讨论：
初始条件
$$
\begin{cases}
f_{0,0}=0,g_{0,0}=1&\\
f_{0,j}=-\infty,g_{0,j}=0&(j\in[1,V])
\end{cases}
$$最终结果
$$
\sum_{\mathclap{\substack{i,j \ i + j = f_{i,j}}}} (i + j)
$$代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int N = 1e3 + 10;
const int MOD = 1e9 + 7;
int n, V, ans, cnt, f[N], g[N];
int main() {
std::cin >> n >> V;
memset(f, -0x3f, sizeof(f));
f[0] = 0, g[0] = 1;
for (int i = 1, v, w; i <= n; ++i) {
std::cin >> v >> w;
for (int j = V; j >= v; --j) {
int mx = std::max(f[j], f[j - v] + w), s = 0;
if (mx == f[j]) s = g[j];
if (mx == f[j - v] + w) (s += g[j - v]) %= MOD;
f[j] = mx, g[j] = s;
}
}
ans = *std::max_element(f, f + V + 1);
for (int i = 0; i <= V; ++i)
if (f[i] == ans) cnt += g[i];
std::cout << cnt << std::endl;
return 0;
}背包问题求具体方案
题目描述
状态表示
集合
属性
状态转移
$$
f_{i,j}\gets \max\{f_{i+1,j},f_{i+1,j-v_i}+w_i\}
$$初始条件
获得方案
提供一组数据：
输入
1
2
3
4
54 5
1 2
2 4
3 4
4 6输出 1（倒着定义）
1
1 4
输出 2（正着定义）
1
1 2
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N = 1e3 + 10; // 假设 n,V 同阶
int n, V, v[N], w[N], f[N][N]; // 此时不能压成一维了
int main() {
std::cin >> n >> V;
for (int i = 1; i <= n; ++i) std::cin >> v[i] >> w[i];
for (int i = n; i; --i)
for (int j = 0; j <= V; ++j) {
f[i][j] = f[i + 1][j];
if (j >= v[i]) f[i][j] = std::max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
int j = V; // 剩余空间的体积
for (int i = 1; i <= n; ++i) {
if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) { // 从选第 i 个的情况转移过来
std::cout << i << " ";
j -= v[i];
}
}
std::cout << std::endl;
return 0;
}可达性背包
$$
f_j=f_{j-v_i}
$$