背包九讲--阅读笔记

背包九讲

很古老的文章， from 2007， 比我年龄都大。 但是确实写得很好。

01背包

很基础。 设 \(f[i][j]\) 为考虑前 \(i\) 个物品， 背包容量为 \(j\) 的最大价值。

$f[i][j] = max { f[i - 1][j], f[i - 1][j - w[i]] + c[i] } $

考虑可以滚动数组， 但更高妙的， 是倒序枚举 \(j\)， 即：

$f[j] = max { f[j], f[j - w[i]] + c[i] } $

完全背包

\(f[i][j] = max\{f[i][j], f[i][j - w[i]] + c[i]\}\)

典中典， 考虑滚动数组， 因为我们要在 \(f[i][j - w[i]], f[i][j]\) 的基础上决策， 所以正序枚举。

多重背包

每个物品可以选 \(k[i]\) 个， 考虑这个限制， 先当成 01 背包做。

\(f[i][j] = max\{f[i - 1][j], f[i - 1][j - k * w[i]] + k * c[i]\}\)

同样可以滚动数组， 优化时间复杂度的话可以二进制拆分。

分组背包

我觉得这是很妙的一个背包， 限制每个组最多选一个物品。

设 \(f[i][j]\) 表示考虑前 \(i\) 组的物品， 背包容量为 \(j\) 的最大价值。

\(f[i][j] = max\{f[i - 1][j], f[i - 1][j - w[k]] + c[k]\}\)

有依赖的背包

考虑简单情况， 有若干个主件， 每个主件有若干个附件， 要想选附件必须先选择主件， 求最大价值。

考虑枚举的思路， 每个主件选哪些附件一共有 \(2^n\) 种策略，我们要在这些策略中选出一个最优的， 那这不是分组背包？ 但是 \(2^n\) 个物品是难以承受的， 但是， 我们可以抽象一点， 先在附件里算 01 背包， 然后就可以得到 \(V - w[i]\) 个物品， 可以承受。 \(w[i]\) 是主件容量。

这其实是很重要思想， 后面在泛化背包里会讲到。 然后我们就可以在若干个阻力算分组背包了。

再复杂一点， 依赖关系构成一课树， 要想选儿子， 必须选爸爸。 其实就是树形DP， 但是用背包去理解的我觉得更加深刻了。

考虑每一棵子树。 设 \(f[u][i][j]\) 表示考虑 \(u\) 的前 \(i\) 个儿子， 容量为 \(j\) 的最大价值。
我们依旧是把 \(f[v][num_son][i]\) 当成 \(v\) 这个组别里的 \(V\) 个物品， 然后就是分组背包。

\(f[u][i][j] = max\{f[u][i - 1][j], f[u][i - 1][j - k] + f[v][num_son][k]\}\)

考虑滚动数组， 可以把第二维滚掉， 倒序枚举即可。
则有
\(f[u][j] = max\{f[u][j], f[u][j - k] + f[v][k]\}\)

是不是很熟悉的树型DP。

泛化物品

考虑一个物品是固定的 \(w\)， \(c\)。 前面提到可以把 \(f[i][v]\) 当成新的物品。 这些我们都可以抽象成一个函数， 函数上的点就是需要考虑的， 这样子理解就可以把他们都当成物品， 从逻辑上就会清晰易懂一些。