【笔记】背包 dp

正在看著名的背包九讲，做点笔记 。

重要的状态转移方程

应该是最原始的那个 。

[F[i][v] = max(F[i - 1][v], F[i - 1][v - c] + w) ]

说是很多背包的状态转移方程就是由这个变式来的……

01背包和完全背包

01背包

代码

for (int i = 1; i <= n; ++i)
  for (int v = vmax; v >= c[i]; --v)
    F[v] = max(F[v], F[v - c[i]] + w[i]);

一个小常数优化

将第二维枚举的下限改成 (max(c[i], vmax - sum{c[i + 1 … n]})) 。

可以用前缀和快速求出 。

原理：

• 明确目标：求出 (F[n][v]) 。

• 可以假设，当 (F[i][v]) 已经求了出来，用此更新 (F[n][v]) 。

• 可以看出，中途 (v) 的最小值就是之后所有的物品都被装进背包里 。

• 因此，用于更新 (F[n][v]) 的状态的 (v) 的最小值就是当前物品之后所有的物品都被装进背包里的时候 。

• 即 (vmax - sum{c[i + 1 … n]}) 。

完全背包

代码

for (int i = 1; i <= n; ++i)
  for (int v = c[i]; v <= vmax; ++v)
    F[v] = max(F[v], F[v - c[i]] + w[i]);

一些小优化

• 对于 (c[i] < c[j]) 并且 (w[i] > w[j]) 的 (j) 物品，可以直接扔掉 。

• 可以把 (c[i] > vmax) 的 (i) 物品扔掉 。

• 可以在若干个 (c[i]) 相等的物品中找到 (w[i]) 最大的 。

一个二进制优化

• 每种物品最多选取 (lfloor frac{vmax}{c[i]} floor) 个 。

• 将每种物品拆分成 (2^0、2^1、2^2 cdots 2^{k - 1}、lfloor frac{vmax}{c[i]} floor - 2^k + 1) 个，其中 (lfloor frac{vmax}{c[i]} floor - 2^k + 1 geq 0)，(k) 是能取到的最大的整数 。

• 因此可以将每种物品看做 (2^0 imes c[i], ~2^0 imes w[i] cdots (lfloor frac{vmax}{c[i]} floor - 2^k + 1) imes c[i], ~(lfloor frac{vmax}{c[i]} floor - 2^k + 1) imes w[i])，保证 ((lfloor frac{vmax}{c[i]} floor - 2^k + 1) imes c[i] leq vmax) 。

• 由于每个数字都能由二进制表示出，因此拆分出的多组同种物品可以组出小于等于 (lfloor frac{vmax}{c[i]} floor) 的所有数字 。

• 每种物品的复杂度此时降到了 (Theta(log⌊frac{V}{C_i}⌋)) 。

代码区别

之前一直搞不懂为什么 (v) 的枚举顺序变了一下就不一样了，只是死记硬背下来，现在搞懂了。

• (F[v] = max(F[v], F[v - c[i]] + w[i])) 是最原始式子的优化，把一维优化掉了 。

• 因此在01背包中，要保证 (F[v]) 存的是 (F[i - 1][v])，之后再进行状态转移 。

• 由于 (v) 是逆序枚举，因此当 (v) 改变了后，被刷新状态的 (F[v]) 中的 (v) 与当前的 (v) 比较更大 。

• 因而当前的 (F[v]) 用来刷新的 (F[v - c[i]]) 还是上一个被枚举的 (i) 刷新的，保证了 (F[v]) 存的是 (F[i - 1][v]) 而不是 (F[i][v]) 。

完全背包同理 。

初始化 dp 数组

要求恰好装满背包

memset(F, -1, sizeof F);
F[0] = 0;

背包可以不被装满

memset(F, 0, sizeof F);

解释

可以从背包空间为 (0)，物品数量为 (0) 的角度考虑 。

• 第一种情况中 (-1) 代表未定义，因此此时只有 (f[0][0] = 0)，保证了恰好装满背包 。

• 第二种情况可以看作所有状态都为空，也就是可以为 (0)，代表可以不被装满 。

多重背包

与01背包的区别：每种物品有规定的数量

代码

for (int i = 1; i <= n; ++i)
  for (int k = 1; k <= m[i] && (k * c[i]) <= vmax; ++k)
    for (int v = vmax; v >= k * c[i]; --v)
      F[v] = max(F[v], F[v - k * c[i]] + k * w[i]);

二进制优化

代码：

for (int i = 1; i <= n; ++i) {
  if (m[i] * c[i] >= vmax) {
    for (int v = c[i]; v <= vmax; ++v)
      F[v] = max(F[v], F[v - c[i]] + w[i]);
    continue;
  }
  int num = min(m[i], vmax / c[i]);
  for (int k = 1; num > 0; k <<= 1) {
    if (num < k) k = num;
    num -= k;
    for (int v = vmax; v >= k * c[i]; --v)
      F[v] = max(F[v], F[v - k * c[i]] + k * w[i]);
  }
}

当然也可以这样：

void Pre() {
  for (int i = 1; i <= n; ++i) {
    if (m[i] == 1) {
      C[++cnt] = c[i];
      W[cnt] = w[i];
      continue;
    }
    int num = min(m[i], vmax / c[i]);
    if (m[i] == 0) num = vmax / c[i];
    for (int k = 1; num > 0; k <<= 1) {
      if (k > num) k = num;
      num -= k;
      C[++cnt] = k * c[i];
      W[cnt] = k * w[i];
    }
  }
}
for (int i = 1; i <= cnt; ++i)
  for (int v = vmax; v >= C[i]; --v)
    F[v] = max(F[v], F[v - C[i]] + W[i]);

可行性判断

题目：每种有若干件的物品能否填满给定容量的背包 。

设 (F[i][j]) 表示用了前 (i) 种物品填满容量为 (j) 的背包后，最多还剩下几个第 (i) 种物品可用 。

代码：

memset(F, -1, sizeof F);
F[0][0] = 0;
for (int i = 1; i <= n; ++i) {
  for (int v = 0; v <= vmax; ++v) {
    if (F[i - 1][v] >= 0) F[i][v] = m[i];
    else F[i][v] = -1;
  }
  for (int v = 0; v <= vmax - c[i]; ++v)
    if (F[i][v] > 0)
      F[i][v + c[i]] = max(F[i][v + c[i]], F[i][v] - 1);
}

混合三种背包

最外层枚举不变，剩下的加个判断硬往上套就行了~~

二维费用背包

代码

for (int i = 1; i <= n; ++i)
  for (int v1 = vmax1; v1 >= c1[i]; --v1)
    for (int v2 = vmax2; v2 >= c2[i]; --v2)
      F[v1][v2] = max(F[v1][v2], F[v1 - c1[i]][v2 - c2[i]] + w[i]);

隐藏在题意下的二维费用背包：

每件物品最多取 (U) 件：可以将件数看做是一维费用，每取一件费用为 (1) 。

分组背包

代码

for (int k = 1; k <= knum; ++k)
  for (int v = vmax; v >= 0; --v)
    for (int i = 1; i <= n[k]; ++i)
      if (v >= c[i]) F[v] = max(F[v], F[v - c[i]] + w[i]);

(k) 是指枚举的第 (k) 组物品，(v) 枚举的是体积，(i) 枚举的是第 (k) 组物品中的第 (i) 件物品 。

枚举的顺序不能变

其中由于 (v) 是先于 (i) 枚举的，因此当 (v) 因枚举减小后，(F[v]) 并不会被 (i) 更新，即不会被同组的物品更新 。

相反，如果第 2，3 层枚举交换，

由于 (i) 是先于 (v) 枚举的，因此当 (i) 因枚举增大后，此时所有的 (F[v]) 已经被第 (k) 组的第 (i - 1) 个物品更新过了 。

一些小优化

• 去掉每组物品中费用大价值小的物品

• 排序或取最小值优化 (v) 的下限 。

多重背包是分组背包的一种特殊情况，所以可以用优化多重背包的方法来优化分组背包 。

可以这样看：

多重背包是从同一种物品中选 (0, ~1, ~2 cdots k) 个，分组背包是从同一组物品中选第 (0, ~1, ~2 cdots k) 个 。

多重背包的二进制优化是预处理出 (k) 种物品，所以我们可以预处理出分组背包每一组的 (k) 件物品 。

然而我并不知道怎么处理，不过这并不重要

说不定我哪天会了就放上来了呢

有依赖的背包

定义：(i) 依赖于 (j) 的意思是，选择了 (i) 物品就必须选择 (j) 物品 。

代码

for (int i = 1, k; i <= m; ++i) {
  c[i] = read(); w[i] = read(); k = read();
  if (k == 0) zhu[++knum] = i;
  else S[k].push_back(i);
} // 读入第 i 件物品的费用、价值、所依赖的主件，将主件存下，把附件存到主件下
for (int k = 1; k <= knum; ++k) { // 枚举主件所在的组
  n = S[zhu[k]].size();
  for (int j = 0, i; j < n; ++j) {
    i = S[zhu[k]][j]; // 枚举该主件下的附件
    for (int v = vmax; v >= c[i]; --v) // 用01背包得出第 k 件主件下附件的各最大价值
      f[k][v] = max(f[k][v], f[k][v - c[i]] + w[i]);
  }
}
for (int k = 1; k <= knum; ++k) // 枚举主件
  for (int v = vmax; v >= 0; --v) // 枚举费用
    for (int cv = v - c[zhu[k]]; cv >= 0; --cv) // 枚举该主件下的物品，费用为 cv，价值为 f[k][cv]
       ans[v] = max(ans[v], ans[v - cv - c[zhu[k]]] + f[k][cv] + w[zhu[k]]); // 分组背包，把主件的费用和价值算上

这是所有物品分为主件和附件的背包，一个附件只能有一个主件，而一个主件能有若干个附件 。

先对主件 (k) 的附件集合进行一次01背包，得到费用依次为 (0、1、2 cdots vmax - c[k]) 的物品，数量为 (vmax - c[k] + 1) 。

每件物品与主件组成 (vmax - c[k] + 1) 种方案，把每个方案看做成一个物品，共同在第 (k) 组物品组里 。

第 (k) 组物品组里的每个物品的费用依次为 (0、c[k]、c[k] + 1、c[k] + 2 cdots vmax)，其中 (0) 是不选第 (k) 组物品组里的物品 。

价值依次为 (0、F[k][0] + w[k]、F[k][1] + w[k]、F[k][2] + w[k] cdots F[k][vmax - c[k]] + w[k]) 。

其他的一些拓展

有森林关系的有依赖的背包，其本质是树形dp，就要看下面的泛化物品了 。

泛化物品

这时候就需要度娘了呢~~

概念

一种物品，它并没有固定的费用和价值，而它的价值随着你分配给它的费用而变化，可以看做是一个函数 。

所有的物品都可以被看做是泛化物品

• 01背包中的物品：仅有 (h(c) = w)，剩下的都为 (0) 。

• 完全背包中的物品：仅有 (h(c) = w, ~h(2c) = 2w, ~h(3c) = 3w cdots h(kc) = kw ~(k leq frac{vmax}{c} ~且~ k in Z^+))，剩下的都为 (0) 。

• 多重背包中的物品：仅有 (h(c) = w, ~h(2c) = 2w, ~h(3c) = 3w cdots h(kc) = kw ~(k leq min(m, ~frac{vmax}{c}) ~且~ k in Z^+))，剩下的都为 (0) 。

• 二维费用背包中的物品：仅有 (h(c1, ~c2) = w)，剩下的都为 (0) 。

• 分组背包中的物品：把一个物品组看作成一个泛化物品，若物品组中存在费用为 (c) 的物品，则 (h(c)) 取值为所有费用为 (c) 的物品的最大价值，剩下的都为 (0) 。

• 有依赖的背包中的物品：每个主件及其附件集合等价于一个物品组，可看作一个泛化物品 。

泛化物品的和的公式

[F(v) = max(h(k) + l(v − k)), ~(0 leq k leq v) ]

泛化物品的背包问题

对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程

若问题的和为 (F) 函数，则答案就是 (F(0 cdots vmax)) 中的最大值 。

持续更新