浅谈背包DP

__newbie__ · 2022-10-21 15:23:28 · 个人记录

前言

背包 DP：求一定代价的最优装载问题

发现 oiwiki 上这一章讲得挺好的。

背包DP

01背包

01 背包：每种物品有它的价值 v_i，重量 w_i。每种物品只有一个，只有选与不选两种操作。

从一道例题入手：

例1：P1048 [NOIP2005 普及组] 采药

对此，我们有两种状态设计方案。

状态设计-方案 1：定义 f(i,j) 表示考虑前 i 种草药用 j 的时间能获得的最大价值。

转移：

由于只有选与不选两种方案，故：

f(i,j)->f(i+1,j)

或：

f(i,j)->f(i+1,j+w_i)

我们只需要保留每个分组的最优状态，通过逆推可得出：

f(i,j) = max(f(i-1,j),f(i-1,j-w_i)+v_i)(w_i \le j)

如果 w_i>j，则只有一个转移：

f(i,j) = f(i-1,j)(w_i>j)

初始化状态：

由于是取最大价值，默认的 0 就是极劣值，不用初始化。

目标状态：

考虑所有草药，花费所有时间获得的最大价值。即 f(m,t)

代码很简单：

#include <bits/stdc++.h>

using namespace std;

int T, M, t[105], w[105], f[105][1005];

int main() {
  cin >> T >> M;
  for (int i = 1; i <= M; i++) {
    cin >> t[i] >> w[i];
  }
  for (int i = 1; i <= M; i++) {
    for (int j = 0; j <= T; j++) {
      if (t[i] > j) {
        f[i][j] = f[i - 1][j];
      } else {
        f[i][j] = max(f[i - 1][j], f[i - 1][j - t[i]] + w[i]);
      }
    }
  }
  cout << f[M][T] << '\n';
  return 0;
}

由上，我们可以总结出 DP 的解题步骤：

1. 状态设计

2. 推导转移方程（通常是收集型）

3. 初始化状态

4. 思考目标状态

状态设计-方案 2：定义 f(i,j) 表示考虑前 i 种草药得到 j 的价值花费的最少时间。

// 洛谷上居然没有这种方法的题解？？？

转移：

f(i,j) = min(f(i-1,j),f(i-1,j-v_i)+w_i)(v_i \le j)

f(i,j) = f(i-1,j)(v_i>j)

初始化：

由于是最小值，0 反而变成了最优状态。考虑初始时全部设为 inf。

分析初始状态，考虑前 i 种草药得到 0 的价值所用空间一定是 0，这是存在的状态，它不能由转移方程递推得出，故将所有的 f(i,0)(0\le i\le m) 设为 0。而反观考虑前 0 种草药得到不为 0 的价值，这显然是一种不存在的状态，将所有的 f(0,j)(1\le j\le \sum{a_i})设为 inf。

目标状态：

由于我们不是按照非最优化属性进行分组，所以我们要间接求出目标状态。

考虑枚举 f(m,j)(1\le j\le\sum a_i)，当 f(m,j) \le t 时，合题意，记录下 j 的值，答案即是最大的 j 值。

代码：

#include <bits/stdc++.h>

using namespace std;

const int T = 1005, M = 105, inf = 1e9;

int t, m, ans = inf, sum, v[M], w[M];
int f[M][M * T], dp[M][T];

int main() {
  cin >> t >> m;
  for (int i = 1; i <= m; i++) {
    cin >> w[i] >> v[i];
    sum += v[i];
  }
  fill(f[0], f[m + 1], inf);
  for (int i = 0; i <= m; i++) {
    f[i][0] = 0;
  }
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= sum; j++) {
      if (j < v[i]) {
        f[i][j] = f[i - 1][j];
      } else {
        f[i][j] = min(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
      }
    }
  }
  for (int i = 1; i <= sum; i++) {
    if (f[m][i] <= t) {
      ans = i;
    }
  }
  cout << ans;
  return 0;
}

由上，我们可以归纳出初始化的一些方法：

1.初始状态是合法状态且不能由转移方程得到。

2.对于最优值求解问题，不合法的状态一定要赋一个极劣值，明确这里没有状态。

滚动数组+上下界估算优化 01 背包

例 1 方案 1 的状态转移：

  for (int i = 1; i <= M; i++) {
    for (int j = 0; j <= T; j++) {
      if (t[i] > j) {
        f[i][j] = f[i - 1][j];
      } else {
        f[i][j] = max(f[i - 1][j], f[i - 1][j - t[i]] + w[i]);
      }
    }
  }

我们发现第 i 层的转移总是与第 i-1 层有关，那么如果我们倒着转移，不就是上一层的状态吗？这样就优化了整整一维。

  for (int i = 1; i <= M; i++) {
    for (int j = T; j >= 1; j--) {
      if (t[i] > j) {
        f[j] = f[j];
      } else {
        f[j] = max(f[j], f[j - t[i]] + w[i]);
      }
    }
  }

还可以更加简化：

  for (int i = 1; i <= M; i++) {
    for (int j = T; j >= t[i]; j--) { 
      f[j] = max(f[j], f[j - t[i]] + w[i]);
    }
  }

另外，有时候我们可以估算出当前状态的上下界，可以免于计算大量不存在状态——时间上的大常数优化。

例 1 方案 2 滚动数组 + 上下界估算：

  for (int i = 1; i <= m; i++) {
    cin >> w[i] >> v[i];
    sum += v[i];
  }
  fill(f + 1, f + sum + 1, inf);
  sum = 0;
  for (int i = 1; i <= m; i++) {
    sum += v[i];
    for (int j = sum; j >= v[i]; j--) {
      f[j] = min(f[j], f[j - v[i]] + w[i]);
    }
  }

空间（优化一维）+ 时间（常数优化）在一些时候真的能派上大用场呢~

完全背包

完全背包：01背包的基础上，每种物品有无限个。

例 1 的升级版：

例2：P1616 疯狂的采药

本题不仅每种物品有无限个，时间与物品数量的范围也加强了很多。考虑使用完全背包。

~~但是我不会啊？~~

我们先用 01 背包的思路做一做。

考虑增加一维来枚举每种物品选的数量，即：

f(i,j)=max(f(i-1,j),f(i-1,j-w_i×k)+v_i×k)

运用本文已述，我们最优可以写出如下代码（我习惯称它为扩展三维 01 背包）：

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

然而这还不够，因为 m×t\le10^7，而上述代码还多了一维 k 的枚举，肯定是要炸时间的。

我们发现 k 的递推有些冗余了，我们可以优化此处的递推。

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

其实这就是完全背包的模型。

我们发现这和 01 背包滚动数组优化后神似，只是 01 背包的 j 的枚举顺序是反向，完全背包是正向。01 背包之所以不能正着转移，是为了避免覆盖上层的状态，而完全背包可以的原因是覆盖后可以递推，与扩展三维 01 背包最终的目的（求出最优的选择数量对应的最优值）是一致的。完全背包相当于每一步都求出了前面的最优状态，后面的可以直接利用上去转移了。

完整代码：

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int M = 1e4 + 5, T = 1e7 + 5;

int t, m, w[M], v[M];
ll f[T];

int main() {
  cin >> t >> m;
  for (int i = 1; i <= m; i++) {
    cin >> w[i] >> v[i];
  }
  for (int i = 1; i <= m; i++) {
    for (int j = w[i]; j <= t; j++) {
      f[j] = max(f[j], f[j - w[i]] + v[i]);
    }
  }
  cout << f[t];
  return 0;
}

多重背包

多重背包：在 01 背包的基础上，每种物品可选 s_i 件

例3：P1776 宝物筛选

考虑扩展三维 01 背包，加一维枚举选的个数。时间复杂度是 O(nw\sum{m_i})，这样你会发现自己得了 50pts 的高分，考虑滚动数组+上界估算，你惊奇的发现这个数字变成了60pts，由于本题不卡空间，你甚至可以将一个物品可选 s_i 件拆成 s_i 件物品做普通 01 背包，这样你就有了 80pts。

然而这还不够，但这能怎么优化呢？如果按照完全背包那样改变枚举顺序，你会发现后面的一些状态只需要前面固定层的最优转移，不好处理。

只能引出二进制分解这个神奇的思想了。

先展示一下做法：

16=1+2+4+8+1

60=1+2+4+8+16+29

43=1+2+4+8+16+12

一般形式：

x=2^0+2^1+...+2^k+(x-2^{k+1}+1)

这样做能够保证 1~x 的任何数都能被表示出来，简单的公理，正如任何整数都可以被只含 01 的二进制整数表示一样不必证明。

代码可以这么写：

  for (int i = 1; i <= n; i++) {
    for (int j = 1, num = m[i]; num > 0; num -= j, j = min(j * 2, num)) {
      for (int k = t; k >= w[i] * j; k--) {
        dp[k] = max(dp[k], dp[k - w[i] * j] + v[i] * j);
      }
    }
  }

这里融合了滚动数组+上下界估算优化，梳理一下代码运行的流程。

第 1 轮 k 循环运行：dp_{w_i}~dp_t 在选 1 个和 0 个中取最优。更新答案。
第 2 轮 k 循环运行：dp_{2w_i}~dp_t 在第 1 轮的基础上选 0 个或者选 2 个。
若第 1 轮最优解为选 0 个，此时等于在选 2 个和选 0 个中取最优。
若第 1 轮最优解为选 1 个，此时等于在选 3 个和选 1 个中取最优。
故第 2 轮将选 0,1,2,3 的所有可能性都考虑了一遍。
……

注意到每一层循环范围都以指数级缩减，这样时间复杂度优化为 O(nw~log\sum{w_i})。嗷嗷快。

温馨提示：二进制优化并不适用价值相等不可区分的方案数多重背包，因为一个数可能被凑出来多次从而算重。

神犇的回答：

混合背包

混合背包：同时包含 01 背包，完全背包，多重背包

例4：樱花

无话可说，只需要判断一下是哪种背包，套模板即可，01 背包可以看做是只选一个的多重背包。本题最好使用 scanf 对应读入。

二维费用背包

二维费用背包：在 01 背包的基础上会消耗多种不同费用（如时间、金钱就不同）

例5：榨取kkksc03

多开一维枚举时间，枚举方式和金钱那一维是一样的，方程：

f(i,j,k)=max(f(i-1,j,k),f(i-1,j-c_i,k-t_i))

真正理解了状态的转移，就会觉得这也太 EZ 了吧。

分组背包

分组背包：将 01 背包的物品分组，每组的物品相互冲突（即每组最多选一个）

例6：通天之分组背包

经典的分组背包，有点意思。

本题没有明确分组范围，建议用 vector 优化空间。

网上有很多分组背包的模板：

  for (int i = 1; i <= cnt; i++) { // 枚举组号
    for (int j = m; j >= 0; j--) { // 枚举重量
      for (int k = 1; k <= t[i][0]; k++) { // 枚举组中元素
        if (j >= a[t[i][k]]) {
          dp[j] = max(dp[j], dp[j - a[t[i][k]]] + b[t[i][k]]);
        }
      }
    }
  }

对比一下三维扩展 01 背包：

  for (int i = 1; i <= n; i++) {
    for (int j = t; j >= 0; j--) {
      for (int k = 1; w[i] * k <= j && k <= m[i]; k++) {
        dp[j] = max(dp[j], dp[j - w[i] * k] + v[i] * k);
      }
    }
  }

可以发现，分组背包的 k 循环是枚举分组中每个物品作为最优转移，而三位扩展 01 背包则是枚举选的个数作为最优转移。

但是他们并没有说清楚，为什么拓扑序长这样？为什么不能交换循环的顺序。

回根溯源，面对这样一个问题，我们不难想到。定义 f(i,j) 表示考虑前 i 组用 j 的容量获得的最大价值。转移：

f(i,j) = max(f(i-1,j),f(i-1,j-w(t(i,k)))+v(t(i,k)))

其中 t(i,k) 表示第 i 组第 k 个物品对应的存储编号。

注意：网上有很多不恰当的比喻，比如将分组背包类比为对每个分组做一次 01 背包，这是完全错误的（每组只能选一个，和 01 背包完全就是不同概念）。

正是因为它的本源长这样，所以才有了上面滚动数组优化后的代码。

这启发了我们：在面对一个不够熟悉的 DP 问题时，一定是先分析它的本源形式，再优化。（不要一上来就是一维滚动数组）

完整代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, m, a[N], b[N], c, p[N], dp[N], cnt;
vector<int> t[N];

int main() {
  cin >> m >> n;
  for (int i = 1; i <= n; i++) {
    t[i].push_back(0);
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i] >> c;
    t[c].push_back(i), t[c][0]++;
    cnt = max(cnt, c);
  }
  for (int i = 1; i <= cnt; i++) {
    for (int j = m; j >= 0; j--) {
      for (int k = 1; k <= t[i][0]; k++) {
        if (j >= a[t[i][k]]) {
          dp[j] = max(dp[j], dp[j - a[t[i][k]]] + b[t[i][k]]);
        }
      }
    }
  }
  cout << dp[m] << '\n';
  return 0;
}

依赖背包

依赖背包：在 01 背包的基础上，物品相互依赖，即选一个物品(附件)的前提必须是选了另一个物品(主件)。

例7：金明的预算方案

？？？这不是 HY 的 sb LJM 吗？？？

这厮咋跑 OI 来了？还为我们提供了依赖背包的模板。

金明这题算是依赖背包的极简版，不仅只有一重依赖，且依赖的数量最多为 2。

考虑将主件和附件捆绑，看成一棵树，主件为根，附件为它的两个儿子（可能为空）。这样所有物品就变成了一片森林。。。对于每一棵树我们有几种转移：

不选
只选根
选根+左儿子
选根+右儿子
选根+左右儿子

代码很简单，读者自做不难：

#include <bits/stdc++.h>

using namespace std;

const int N = 32005;

struct T{
  int w, v, q, son[3];
} a[N];

int n, m, dp[N];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> a[i].w >> a[i].v >> a[i].q;
    a[i].v *= a[i].w;
    if (a[i].q != 0) {
      a[a[i].q].son[++a[a[i].q].son[0]] = i;
    }
  }
  for (int i = 1; i <= m; i++) {
    for (int j = n; a[i].q == 0 && j >= a[i].w; j--) {
      int son1 = a[i].son[1], son2 = a[i].son[2];
      dp[j] = max(dp[j], dp[j - a[i].w] + a[i].v);
      if (son1 && j >= a[i].w + a[son1].w) {
        dp[j] = max(dp[j], dp[j - a[i].w - a[son1].w] + a[i].v + a[son1].v);
      }
      if (son2 && j >= a[i].w + a[son2].w) {
        dp[j] = max(dp[j], dp[j - a[i].w - a[son2].w] + a[i].v + a[son2].v);
      }
      if (son1 && son2 && j >= a[i].w + a[son1].w + a[son2].w) {
        dp[j] = max(dp[j], dp[j - a[i].w - a[son1].w - a[son2].w] + a[i].v + a[son1].v + a[son2].v);
      }
    }
  }
  cout << dp[n] << '\n';
  return 0;
}

感觉直接这么枚举方案普遍性还是不够。。。而且，如果有 k 个附件，差不多有 2^k+1 种方案数。这 TM 复杂度太高了吧。~~然鹅此时的我并不会其他解。~~

如果有多重依赖呢？那么应该就可以算到树形背包的范畴里了，大概是利用递归逐层上浮最优值。