背包 dp

01 背包

给你 \(n\) 个物品，\(m\) 的容量，每个物品有体积 \(v_i\) 和价值 \(w_i\)，问你能获得的价值 \(\max\)。

考虑设计一个状态 \(dp(i, j)\) 表示考虑前 \(i\) 个物品，至多使用了 \(j\) 的空间的最大价值。

考虑对于 \(i\) 的决策有什么，无非就是选 \(i\) 或者不选 \(i\)，以此为依据我们可以把所有满足在前 \(i\) 个物品里面至多用 \(j\) 的空间的所有决策分类。

第一类就是不选 \(i\) 这个物品的，第二类就是选 \(i\) 这个物品的。

那么从第一类转移过来就是 \(dp(i - 1, j) \to dp(i, j)\)。

从第二类转移过来，因为第二类都选了 \(i\) 这个物品，所以是 \(dp(i - 1, j - v_i) + w_i \to dp(i, j)\)。

那么因为属性是代价的最大值，所以我们考虑在这两种决策里面选最大值即可。

可以得到状态转移方程：

\[ dp(i, j) = \max(dp(i - 1, j), dp(i - 1, j - v_i) + w_i (\text{if } j \ge v_i.)) \]

可以检查一下，发现当前阶段（考虑物品 \(i\) 的）状态都由 \(i - 1\) 阶段转移过来，那么状态转移是不成环的，显然无后效性。

这里使用了集合的思想考虑决策，可以发现显然覆盖了完整的状态空间，正确性没有问题。

然后考虑怎么初始化，根据状态的定义，这里不是恰好是至多，所以只需要令所有状态初始均为 \(0\) 即可，（在没有决策之前，至多使用任意的空间能获得的最大价值都是 \(0\)。）

答案（目标状态），根据定义就是 \(dp(n, m)\)。

那么就可以愉快的写代码了。

memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; ++i)
  for(int j = 0; j <= m; ++j) {
    dp[i][j] = dp[i - 1][j];
    if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
  }
cout << dp[n][m] << endl;

然后注意到这个状态的当前阶段只依赖于上一个阶段，所以我们可以利用一个叫滚动数组的技巧，每次只保存上一个阶段和这一个阶段的状态，在这两个数组里面不断转移即可：

int dp[2][si];

memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; ++i) {
  int now = i & 1, last = (i & 1) ^ 1;
  for(int j = 0; j <= m; ++j) {
    dp[now][j] = dp[last][j];
    if(j >= v[i]) dp[now][j] = max(dp[now][j], dp[last][j - v[i]] + w[i]);
  }
}
cout << dp[n & 1][m] << endl;

发现其实还能再优化，注意到我们每种物品只有一个，所以 \(dp(i, j)\) 必然是从上一个阶段的一个 \(j^\prime < j\) 转移过来的（\(v_i > 0\)）。

如果我们把这两维压缩到一起，虽然是直接继承上一个阶段了，但是直接转移显然有问题，因为 \(dp(j)\) 会依赖 \(dp(j - v_i)\)，而正着循环 \(j\) 会导致 \(dp(j -v_i)\) 提前被更新成 \(i\) 阶段的 \(dp(j - v_i)\)，所以需要使用倒序循环来保证转移不成环。

那么可以写出代码：

int dp[si];

memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; ++i)
  for(int j = m; j >= v[i]; --j)
    dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
  // 因为直接共用一个数组了，所以不用手动继承上一个阶段了。
cout << dp[m] << endl;

完全背包

给你 \(n\) 种物品，\(m\) 的容量，每种物品有体积 \(v_i\) 和价值 \(w_i\)，每种物品可以有无穷多个，问你能获得的价值 \(\max\)。

依旧考虑沿用 01 背包的状态，设 \(dp(i, j)\) 表示考虑前 \(i\) 个物品，至多使用了 \(j\) 的空间的最大价值。

但显然这里的决策不太一样了，因为每种物品都有无限多个，所以决策可能会在某种物品上决策多次，转移就可能在同阶段转移。

那么分类讨论看看能从什么地方转移过来。

首先如果我们不选这种物品的任意一个，算是一种，转移会变成 \(dp(i - 1,j) \to dp(i, j)\)。

然后如果我们选了这种物品的一个，转移会变成 \(dp(i - 1, j - v_i) + w_i\to dp(i, j)\)。

如果选了两个，转移会变成 \(dp(i - 1, j - 2v_i) + w_i \to dp(i, j - v_i) + w_i \to dp(i, j)\)。

我们不希望一次决策两个状态，所以实际上选两个是以选了一个的状态作为基础再选一个的。

那么对于每个 \(j\) 就可以得到一个转移：从上一阶段的 \(dp(j)\) 或者 \(dp(j - v_i)\) 转移过来，从这一阶段的 \(dp(j - v_i)\) 转移过来。

然后我们发现这个转移显然会重复转移很多，画图可以发现省去 \(dp(i - 1,j - v_i)\) 之后状态空间仍然能被覆盖满，所以最终方程变为：

\[ dp(i, j) = \max(dp(i - 1, j), dp(i, j - v_i) + w_i(\text{if } j \ge v_i.)) \]

（在设计普通的 dp 的时候状态转移可以有重复（求 max/min 的时候），但是不能漏掉状态，但是计数 dp 就不一样了，要同时满足不重不漏！）

类似 01 背包，我们可以把它滚动数组变成 \(2V\) 的空间，不过它也是可以直接缩掉一维的。

具体来说，从上一个阶段的转移直接继承，而它需要的是这一个阶段的，在它之前的状态，所以正序枚举即可。

那么可以写出代码：

memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; ++i)
  for(int j = v[i]; j <= m; ++j)
    dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[m] << endl;

多重背包

每个物品有多个。

暴力做法是拆成 01 背包做，考虑前 \(i\) 种物品至多用了 \(j\) 的空间的最优代价

然后这个复杂度是 \(O(nm\sum cnt_i)\) 的（有人说是 \(O(m \sum cnt_i)\)，不是很懂）

单调队列优化比较人类智慧，之后来补。

分组背包

有分组，每组最多只能选一个。

体积和代价记为 \(v(i, j)\) 和 \(c(i, j)\)。

依然是很 simple 的，阶段是组，在每一组里面决策一下选哪个就好。

因为是最多所以也可以不选，要覆盖完决策空间。

具体来说，记 \(dp(i, j)\) 表示前 \(i\) 组至多选了 \(j\) 的空间的最大价值。

那么有：\(dp(i, j) = \max\limits_{k}\{dp(i - 1, j), dp(i - 1, j - v(i, k) + c(i, k))\}\)。

枚举一下就行，复杂度是 \(O(nV\sum cnt_i)\) 的，

当然这个和 01 背包形式几乎一致，所以也可以以同样的方式优化。

memset(dp, -0x3f, sizeof dp), dp[0] = 0;
for(int i = 1; i <= n; ++i)
  for(int j = m; j >= 0; --j)
    for(int k = 1; k <= cnt[i]; ++k)
      if(j >= v[i][k]) dp[j] = max(dp[j], dp[j - v[i][k]] + c[i][k]);
cout << dp[m] << endl;

树上背包

有依赖的背包，要选儿子要先选父亲。

阶段明显是子树。

设 \(dp(u, i)\) 表示考虑以 \(u\) 为根的子树，至多选了 \(i\) 的空间的最大价值。

转移就是枚举子树的状态把它们合并上来，然后再考虑选不选 \(u\)。

这可以看作一个分组背包的问题，状态转移是：

\(dp(u, i + j) = \max\{dp(u, i) + dp(v, j)\}\)，但是需要判一下是否合法。

注意到其实我们本质上是省略了第二层阶段“\(u\) 的前 \(i\) 颗子树”，所以需要倒序枚举空间。

不过不这么考虑也是很容易想到倒序枚举的，因为 \(i + j\) 依赖于 \(i\) 且我们是在“一颗一颗子树地加入”，所以转移实际上是从上个阶段转移的（这么说好像和上面没区别）

代码不难写出，为了方便处理可以令一个虚拟点 \(0\) 为根，代码里是对于任意一个节点都会先选，所以容量扩大为 \(m + 1\)。

// assume v[i] = 1
// there's a virtual vertex 0 so we should use m + 1.
void dfs(int u, int fa) {
  siz[u] = 1, dp[u][1] = c[i];
  for(int i = head[u]; ~i; i = e[i].Next) {
    int v = e[i].ver;
    if(v == fa) continue;
    dfs(v, u);
    for(int i = min(siz[u], m + 1); i; --i) 
      for(int j = 1; j <= siz[v]; ++j)
        if(i + j <= m + 1) dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j]);
    siz[u] += siz[v];
  }
}

这个 dp 的过程可以看作，\(dp(u, j)\) 是之前已经合并好的子树，每次枚举两个子树合并起来。

这种，把子树状态合并到根节点状态的，通常都需要额外设置一个阶段“前 \(i\) 颗子树”以确保正确性。

这里体积为 \(1\)，所以其实复杂度是平方而不是立方的，具体原因可以看树形 dp 部分。

状态的至多，恰好，至少

最主要的区别就是他们的字面意思，使用对应状态的时候要想清楚这种对应的状态要怎么写。

初始值和终态要根据状态本身的定义来写。

这里假定需要求解的问题是普通的01背包，状态设计为二维，无滚动数组，只需要价值最大即可，没有恰好装满的条件。

• 恰好

完整的状态是：考虑从前 \(i\) 个物品里面选，恰好用 \(j\) 的空间的所有方案，权值和的最大值。

因为 \(dp(0, *)\) 系的状态就是所有的考虑从前 \(0\) 个物品里选（不选）的情况。

所以在“恰好”的约束下，只有 \(dp(0,0) = 0\) ,也就是恰好用 \(0\) 的空间才是合法的。

其他的不合法条件都要设置为 \(-\infty\) ，（不仅表示“不合法”，也是为了之后转移）

所以会这么写：

memset(dp, -0x3f, sizeof dp), dp[0][0] = 0;

那么，在 dp 完了之后，我们需要扫描 \(dp(n,*)\) 系的状态，因为装不满也有可能是最值（当前问题没有恰好的限制，如果有，直接输出终态即可）。

（不论有没有滚动数组优化都需要）

• 至多

完整的状态是：考虑从前 \(i\) 个物品里面选，用不超过 \(j\) 的空间的所有方案，权值和的最大值。

因为这里的限制是不超过，所以 \(dp(0,*)\) 系的所有状态都是合法的。

你想，你不选任何物品，那自然所有可能的空间的不会超过啊。

所以初始值全部设置为 \(0\)。

那么，在 dp 完了之后，直接输出终态 \(dp(n,m)\) 即可，（毕竟状态设计的是“所有方案”）

因为至多和恰好都适用于 “最大”，所以放在上面，而至少适用于“最小”，所以单独分离（不过恰好也是可以做的，道理一样）

问题：你至少需要用 \(j\) 的空间，求价值的最小值。

• 至少

完整的状态是：考虑从前 \(i\) 个物品当中选，至少用 \(j\) 的空间的所有方案，权值和的最小值。

状态转移方程是和上面差不多的，不过初始化和转移方式需要改变。

因为当你不选的时候，只有 \(dp(0,0) = 0\) 是合法的，所以其他的设置为 \(+\infty\)。

memset(dp, 0x3f, sizeof dp), dp[0][0] = 0;

但是转移就略有不同了。

如果说，你枚举到的 \(j\) 没有办法满足当前 \(v_i\) 的需求，不应该只是继承上一轮的状态。

因为，在不考虑访问无效下标的情况下，\(dp(i,j)=\min\{dp(i-1,j-v_i)\},(j-v_i<0)\) 也是合法的转移。

至少需要负数的空间，那你不选也是满足的啊，\(dp\) 又是记录最小值，自然需要把 \(dp(i-1,j-v_i)=0\) 啊。

所以状态转移方程需要变成这样：（代码写的是二维背包不滚动的情况，其他道理一样）

for(int i = 1; i <= n; ++i)
  for(int j = 0;j <= m; ++j)
      dp[i][j] = dp[i - 1][j], dp[i][j] = min(dp[i][j], dp[i - 1][max(0, j - v[i])] + c[i]);
cout << dp[n][m] << endl;

可撤销背包/可删除背包

一个比较呃呃的事情是我以为我不会这个，结果我之前胡出来过这玩意儿但是我没印象了，做题效率不够高导致的。

应该是：ABC321F #(subset sum = K) with Add and Erase 。

今天模拟赛里 T2 需要用，然后似乎就我不会，/ll。

---

注意区分什么是可撤销什么是可删除。

如果硬要做个归类，这里的背包问题形如 \(f(x) = \bigoplus\limits_{(\sum v_{i}) = x}(\bigotimes\limits_{i} W(v_{i}))\)。

可撤销是指能够撤掉最后一个，可删除是可以删掉任何一个。

可撤销的话直接撤掉就行，几乎没啥限制，主要问题在于可删除。

可删除的要求转移时使用的操作必须存在逆运算，不能是 \(\min,\max,\text{or}\) 这样的运算。

所以一般可删除的背包都是方案数背包，对于可行性背包我们可以考虑直接转成方案数，但因为方案数太大所以要取模。

但这样取模之后可能有 \(0\)，这是有问题的，我们可以类似双哈希做两次，只要不对着卡完全没法卡！！！

具体来说如果我们转移形如 \(dp(n, i + v) \gets dp(n - 1, i)\)，那么我们如果想撤销掉 \(n\) 这个物品的贡献，那么令 \(dp(n, i + v)\) 减去 \(dp(n - 1, i)\) 就可以了。

因为需要保证减去的是旧状态，所以对于 01 背包，我们省略了第一维之后是倒序循环，撤销的时候自然就需要是正序循环，完全背包是类似的。

还有一种办法是考虑维护前后缀区间分别的背包，枚举 \(j\)，合并 \(pre(i - 1), i, suf(i + 1)\) 即可。

还有一种办法是考虑序列分治，类似线段树分治一样，不过我感觉没啥用。

---

最后更新: October 23, 2023