背包问题

简述

每个物品有自己的体积和收益。

把一堆如上的物品放进容量有限的背包，使收益最大。

（万能）状态转移方程

\(f_j\) 表示放入的物品的体积为（不超过） \(j\) 的最大收益。

\(v_i\) 表示放入第 \(i\) 个物品的收益，也可以理解为他的价值

\(w_i\) 表示放入第 \(i\) 个物品所消耗掉的体积，也可以理解为他的体积

\[f_j = max(f_j, f_{j - w_i} + v_i)\]

这个方程的意义就是：

当状态为 \(j\) 的时候，有两种途径可以获得 \(f_j\) 的值：不选这第 \(i\) 个物品(\(f_j\))和选第\(i\)个物品(\(f_{j - w_i} + v_i\))。只需要算出这两种途径所带来的收益的最大值就可以了。

再来解释一下选第 \(i\) 个物品的状态转移方程：\(j - w_i\) 表示：当前所花的容量 \(j\) 减去当前选择的物品 \(i\) 的容量 \(w_i\) 表示不选这个物品时的最大收益。加上 \(v_i\) 的意思就是加上这个物品的价值。

即当前收益最大值可以从之前的收益最大值递推出来。

这就是适用于这几种背包的__万能__状态转移方程。

看不懂就再思考思考，玩味个几天就懂了。

~~实在不行背板子~~

那么如何循环呢？

深入了解背包（与大多数DP）的概念

这里我先口胡一下

明白了状转方程之后，我们要考虑如何设计循环了。

这里我们就涉及到了三个重要的概念

阶段、状态、决策

阶段：

求解一个 \(DP\) 问题通常会分为几个离散化（即不连续）的阶段（大多数情况下不连续）的阶段。

就以下文 \(01\)背包为例。

几乎所有的背包都将选择第 \(i\) 个物品作为不同的阶段。

状态：

每一个阶段都会对应几种状态，比如下文中， \(i, j\) 就共同构成了状态。状态可以理解为该阶段下的一些值（比如边权等等）。

几乎所有的背包的状态都是物品的 \(v\) 与 \(w\)。

决策：

决策可以理解为对于该阶段的求解、转移。

决策在背包问题中（应该）只存在于分组背包与多重背包中（当然还有到达型背包）。

顺序：

个人认为所有的 \(DP\) 都遵循这个原则：

循环时，顺序为阶段 \(\rhd\) 状态 \(\rhd\) 决策

循环顺序

01背包

for (int i = 1; i <= n; ++i) {        for (int j = m; j >= w[i]; --j){            f[j] = max(f[j], f[j - w[i]] + v[i]);        }    }

如你所见， \(i\) 为阶段 \(i, j\) 共同组成了状态。决策由 \(i, j\) 组成。

第二层循环为什么要倒序呢？~~因为完全背包是倒序啊！~~

完全背包

for (int i = 1; i <= n; ++i) {        for (int j = w[i]; j <= m; ++j){            f[j] = max(f[j], f[j - w[i]] + v[i]);        }    }

为什么第二层循环是正序呢？~~因为 \(01\) 背包是倒序啊！~~

因为我们在求完全背包的时候状态是可以使用同阶段的其他状态的（即可以取一个物品无限次）。

你也可以自己手推

多重背包

for (int i = 1; i <= n; ++i) {    for (int j = 1; j <= c[i]; ++j) {        for (int k = m; k >= w[i]; --k) {            f[k] = max(f[k], f[k - w[i]] + v[i]);        }    }}

~~暴力的不能再暴力了~~、

可以看出，该时间复杂度很高，为 \(O_{(n\ max(c[i])\ m)}\)

所以以后我们会遇到一个叫 二进制拆分 的一个东西，所以等我学了再来更新 \(qwq\)

分组背包

for (int i = 1; i <= n; ++i) {        for (int j = m; j >= 0; --j) {            for (int k = 1; k <= c[i]; ++k) {                if (j >= w[i][k])                    f[j] = max(f[j], f[j - w[i][k]] + v[i][k]);            }        }    }

分组背包~~是一个十分毒瘤的东西~~，我们在记忆的时候一定要记住，分组背包的状态是使用的 \(w\)，空间，而决策是使用该组的第几个物品。