01 背包

题目描述

有 n 个物品，一个体积为 V 的背包。 第 i 个物品体积为 vi，价值为 wi。 每个物品只能选择一次，最大化放入背包物品的总价值。 输出最大总价值。

状态表示

集合

令 fi, j 表示 从前 i 个物品中选，总体积不超过 j 的方案集合。

属性

集合中的 最大价值。

状态转移

故 fi, j = max {fi − 1, j, fi − 1, j − vi + wi} DP 时间复杂度为 O(nV)。

初始条件

当选择 0 个物品时，无论总体积为多少，总价值都是 0，故 f0, j = 0 (j ∈ [0, V])

最终结果

最终应当是 从前 n 个物品中选，总体积不超过 V 的方案中的最大价值，即 fn, V

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
const int N = 1e3 + 10;

int n, V, f[N];

int main() {
  std::cin >> n >> V;
  for (int i = 1, v, w; i <= n; ++i) {
    std::cin >> v >> w;
    for (int j = V; j >= v; --j) // 使用上一层的，倒序遍历
      f[j] = std::max(f[j], f[j - v] + w);
  }
  std::cout << f[V] << std::endl;
  return 0;
}

完全背包

题目描述

有 n 个物品，一个体积为 V 的背包。 第 i 个物品体积为 vi，价值为 wi。 每个物品可以选择无限次，最大化放入背包物品的总价值。 输出最大总价值。

状态表示

集合

令 fi, j 表示 从前 i 个物品中选，总体积不超过 j 的方案集合。

属性

集合中的 最大价值。

状态转移

这样 DP 的时间复杂度是 O(nV2) 的，有没有优化方法呢？

可以发现 故 fi, j = max {fi, j − vi + wi, fi − 1, j} 此时时间复杂度降为 O(nV)。

初始条件

当选择 0 个物品时，无论总体积为多少，总价值都是 0，故 f0, j = 0 (j ∈ [0, V])

最终结果

最终应当是 从前 n 个物品中选，总体积不超过 V 的方案中的最大价值，即 fn, V

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
const int N = 1e3 + 10;

int n, V, f[N];

int main() {
  std::cin >> n >> V;
  for (int i = 1, v, w; i <= n; ++i) {
    std::cin >> v >> w;
    for (int j = v; j <= V; ++j) // 使用同一层的，正序遍历
      f[j] = std::max(f[j], f[j - v] + w);
  }
  std::cout << f[V] << std::endl;
  return 0;
}

多重背包

题目描述

朴素算法

状态表示

有 n 种物品，一个体积为 V 的背包。 第 i 个物品体积为 vi，价值为 wi。 每个物品可以选择 si 次，最大化放入背包物品的总价值。 输出最大总价值。

集合

令 fi, j 表示 从前 i 种物品中选，总体积不超过 j 的方案集合。

属性

集合中的 最大价值。

状态转移

故

初始条件

当选择 0 个物品时，无论总体积为多少，总价值都是 0，故 f0, j = 0 (j ∈ [0, V])

最终结果

最终应当是 从前 n 种物品中选，总体积不超过 V 的方案中的最大价值，即 fn, V

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
const int N = 110;

int n, V, f[N];

int main() {
  std::cin >> n >> V;
  for (int i = 1, v, w, s; i <= n; ++i) {
    std::cin >> v >> w >> s;
    for (int j = V; ~j; --j) // 一定要把 j 放在外面！使用上一层的，倒序遍历
      for (int k = 0; k <= s && k * v <= j; ++k)
        f[j] = std::max(f[j], f[j - k * v] + k * w);
  }
  std::cout << f[V] << std::endl;
  return 0;
}

二进制优化

引理：

∀ n ∈ ℕ*，n 可以分解为 20, 21, ⋯, 2k, s(20 + 21 + ⋯ + 2k + s = n, s ∈ [0, 2k + 1)。这些数可以凑出 1 ∼ n 中的任何正整数。

证明：

显然地，20, 21, ⋯, 2k 可以凑出 [1, 2k + 1 − 1] 之间的所有正整数。

将其中每个数 +s，则可以凑出 [s, n]​ 之间的所有正整数。

因为 s ≤ 2k + 1 − 1，所以 [1, 2k + 1 − 1], [s, n] 必然能覆盖 [1, n] 中的所有正整数。

证毕。

对于每种物品的个数 s​，我们也可以按照这样的方法拆分，做 01 背包。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
const int N = 2e3 + 10;

int n, V, f[N];

int main() {
  std::cin >> n >> V;
  for (int i = 1, v, w, s; i <= n; ++i) {
    std::cin >> v >> w >> s;
    for (int k = 1; k <= s; k <<= 1) {
      for (int j = V; j >= k * v; --j) // 使用上一层的，倒序遍历
        f[j] = std::max(f[j], f[j - k * v] + k * w);
      s -= k;
    }
    if (s)
      for (int j = V; j >= s * v; --j)
        f[j] = std::max(f[j], f[j - s * v] + s * w);
  }
  std::cout << f[V] << std::endl;
  return 0;
}

单调队列优化

在朴素算法中，状态转移方程如下： fj ← max {fj, fj − v + w, fj − 2v + 2w, fj − 3v + 3w, ⋯, fj − sv + sw}(假设 j ≥ sv) 容易发现，，即这些数同属一个模 m 的同余系。

不同同余系之间不相干，所以我们可以在一个同余系内考虑。

可以发现，求 fj 其实就是求一段长度为 s 的区间的最大值，故考虑使用单调队列。

令非负整数 q ∈ [0, v)，可得如下式子：

上面的最后一个式子只是理想情况，可能取不到 fq。

可以发现在第 1 个式子中是 fq，第 2 个式子中是 fq + w，最后一个式子中为 fq + pw。队列中的值都在变化，是无法使用单调队列的。

怎么办呢？

其实可以把 max  中的 w 都提出来，得到如下式子： 此时队列中原有的元素就不会发生变化了。

虽然在单调队列中插入的只是下标（如 q, q + v, ⋯, q + pv），但是这个下标 r 所代表的值 val (r)​ 为多少呢？

假设 r = m + nv。

通过观察可以发现，w 的系数就是 n，故： 有了 val (r)，就可以解决当前元素插入单调队列队尾的问题了。

然后我们要解决如何判断队头是否过时的问题。

假设当前队头 a = j + xv，当前的体积 b = j + yv(x < y)。

容易发现，当 y − x > s 时，队头就失效了。

又因为 b − a = (y − x)v，所以队头失效的条件为：

最后，我们应该知道如何用单调队列队头 a 来更新 fb​。

朴素式子中第 2 项以以后的元素都是在单调队列中的，所以后面这些值的 max  相当于 val (a)。

因为 b = j + yv，所以 max  外的 w 的系数为 。

故可得： 此时就可以 O(1) 计算 fb 了。

该算法时间复杂度为 O(nV)。

代码实现

PS：具体实现时，如果只开一个一维数组，那么就应当倒序循环。但是如果倒序循环，单调队列就无法优化。所以应该采用滚动数组技巧。此处使用 f 存储这一层，g 存储上一层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
const int N = 2e4 + 10;

int n, V, f[N], g[N], q[N]; // f,g 为 DP 数组，q 为单调队列（最大容量为 V）

int main() {
  std::cin >> n >> V;
  for (int i = 1, v, w, s; i <= n; ++i) {
    std::cin >> v >> w >> s;
    memcpy(g, f, sizeof(f)); // g <- f
    
    for (int j = 0; j < v; ++j) { // 枚举同余类
      int hh = 0, tt = -1; // 单调队列的头和尾
      for (int k = j; k <= V; k += v) { // 在同一个同余类内枚举体积
        while (hh <= tt && k - q[hh] > s * v) ++hh; // 弹出队头
        if (hh <= tt) f[k] = std::max(g[k], g[q[hh]] + (k - q[hh]) / v * w); // 状态转移
        while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) --tt; // 弹出队尾
        q[++tt] = k; // 插入当前元素
      }
    }
  }
  
  std::cout << f[V] << std::endl;
  return 0;
}

混合背包

题目描述

有 n 种物品，一个体积为 V 的背包。

物品一共有三类：

  • 第一类物品只能用 1 次；
  • 第二类物品可以用无限次；
  • 第三类物品最多只能用 si 次。

第 i 种物品，体积为 vi，价值为 wi​。

最大化放入背包物品的总价值，并输出最大总价值。

解决方法

01 背包、完全背包、多重背包的混合版。

可以分类讨论：

  • 对于完全背包，可以单独计算
  • 对于 01 背包，当成 si = 1​ 的多重背包，和多重背包一起计算。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
const int N = 1e3 + 10;

int n, V, f[N];

int main() {
  std::cin >> n >> V;
  for (int i = 1, v, w, s; i <= n; ++i) {
    std::cin >> v >> w >> s; // 本题中 s=-1 为第一类，s=0 为第二类，s 是正整数为第三类
    if (!s) { // 完全背包
      for (int j = v; j <= V; ++j)
        f[j] = std::max(f[j], f[j - v] + w);
    } else {
      if (s == -1) s = 1; // 01 背包->多重背包
      for (int k = 1; k <= s; k <<= 1) {
        for (int j = V; j >= k * v; --j)
          f[j] = std::max(f[j], f[j - k * v] + k * w);
        s -= k;
      }
      if (s)
        for (int j = V; j >= s * v; --j)
          f[j] = std::max(f[j], f[j - s * v] + s * w);
    }
  }
  std::cout << f[V] << std::endl;
  return 0;
}

分组背包

题目描述

有 n 组物品，一个体积为 V 的背包。

第 i 组物品有 si 个，同一组内的物品最多只能选一个。

第 i 组内的第 j 个物品，体积为 vi, j，价值为 wi, j。

最大化放入背包物品的总价值，并输出最大总价值。

状态表示

集合

令 fi, j 表示 从前 i 组物品中选，总体积不超过 j 的方案集合。

属性

集合中的 最大价值。

状态转移

故

初始条件

当从前 0 组物品中选择时，无论总体积为多少，总价值都是 0，故 f0, j = 0 (j ∈ [0, V])

最终结果

最终应当是 从前 n 组物品中选，总体积不超过 V 的方案中的最大价值，即 fn, V

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
const int N = 110; // 假设 V,s[i] 同阶

int n, V, v[N], w[N], f[N];

int main() {
  std::cin >> n >> V;
  for (int i = 1, s; i <= n; ++i) {
    std::cin >> s;
    for (int j = 1; j <= s; ++j) std::cin >> v[j] >> w[j];
    for (int j = V; ~j; --j)
      for (int k = 1; k <= s; ++k)
        if (j >= v[k]) f[j] = std::max(f[j], f[j - v[k]] + w[k]);
  }
  std::cout << f[V] << std::endl;
  return 0;
}

二维费用背包

题目描述

有 n 组物品，一个体积为 V，最大承重为 M 的背包。

第 i 个物品体积为 vi，重量为 mi，价值为 wi。 每个物品只能选择一次，最大化放入背包物品的总价值。 输出最大总价值。

状态表示

集合

令 fi, j, k 表示 从前 i 个物品中选，总体积不超过 j，总重量不超过 k 的方案集合。

属性

集合中的 最大价值。

状态转移

与 01 背包类似，分选择和不选两种情况。

故 fi, j, k = max {fi − 1, j, k, fi − 1, j − vi, k − mi + wi}

初始条件

当选择 0 个物品时，无论总体积、总重量为多少，总价值都是 0，故 f0, j, k = 0 (j ∈ [0, V], k ∈ [0, M])

最终结果

最终应当是 从前 n 个物品中选，总体积不超过 V，总重量不超过 M 的方案中的最大价值，即 fn, V, M

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
const int N = 1e2 + 10;

int n, V, M, f[N][N];

int main() {
  std::cin >> n >> V >> M;
  for (int i = 1, v, m, w; i <= n; ++i) {
    std::cin >> v >> m >> w;
    for (int j = V; j >= v; --j)
      for (int k = M; k >= m; --k)
        f[j][k] = std::max(f[j][k], f[j - v][k - m] + w);
  }
  std::cout << f[V][M] << std::endl;
  return 0;
}

有依赖的背包问题

题目描述

有 n 个物品和一个体积为 V​ 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

第 i 个物品体积为 vi，价值为 wi，依赖的父结点编号为 pi。若 pi = −1​，则表示根节点。

求解将哪些物品装入背包，可使物品总体积不超过背包体积，且总价值最大。

输出最大价值。

状态表示

集合

令 fu, j 表示 在以 u 为根结点的子树中（包含 u），总体积不超过 j 的方案集合。

属性

集合中的 最大价值。

状态转移

对于每个儿子，可以用体积划分集合。

由于每个儿子只能有一种体积，所以相当于一个分组背包。

初始条件

fu, j = 0 (j ∈ [1, n], j ∈ [1, V])

最终结果

最终结果应为在根结点的子树中，总体积不超过 V 的方案集合，即 froot, V root 为树的根结点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
const int N = 110;

std::vector<int> g[N];
int n, V, root, v[N], w[N], f[N][N];

void dp(int u) {
  for (auto son : g[u]) { // 遍历儿子
    dp(son);

    for (int j = V - v[u]; ~j; --j) // 由于一定要包含 u 结点，所以最大体积为 V-v[u]
      for (int k = 0; k <= j; ++k)
        f[u][j] = std::max(f[u][j], f[u][j - k] + f[son][k]);
  }

  for (int i = V; i >= v[u]; --i) f[u][i] = f[u][i - v[u]] + w[u]; // 加入 u，更新
  for (int i = 0; i < v[u]; ++i) f[u][i] = 0; // 不可能的情况
}

int main() {
  std::cin >> n >> V;
  for (int i = 1, p; i <= n; ++i) {
    std::cin >> v[i] >> w[i] >> p;
    if (p == -1) root = i;
    else g[p].push_back(i);
  }
  dp(root);
  std::cout << f[root][V] << std::endl;
  return 0;
}

背包问题求方案数

题目描述

有 n 件物品，体积为 V 的背包。

第 i 件物品体积为 vi，价值为 wi​，每件物品只能用一次。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包体积，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 109 + 7 的结果。

状态表示

集合

令 fi, j 表示从前 i 个物品中选，总体积 恰好 为 j 的方案集合。

属性

集合中的 最大价值。

状态转移

令 gi, j 表示到达 fi, j​ 的方案数。

可以知道， fi, j = max {fi − 1, j, fi − 1, j − vi + wi} 可以分三类讨论：

  • fi − 1, j > fi − 1, j − vi + wi：此时 fi, j ← fi − 1, j。那么 gi, j ← gi − 1, j。
  • fi − 1, j < fi − 1, j − vi + wi：此时 fi, j ← fi − 1, j − vi + wi。那么 gi, j ← gi − 1, j − v。
  • fi − 1, j = fi − 1, j − vi + wi：此时两种前置情况都可以到达 fi, j。那么 gi, j ← gi − 1, j + gi − 1, j − v。

初始条件

由于 fi, j 表示 恰好 总体积为 j 的方案集合，那么

最终结果

令 k 表示背包中的最大总价值，即 f 中的最大值。此时答案为：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
const int N = 1e3 + 10;
const int MOD = 1e9 + 7;

int n, V, ans, cnt, f[N], g[N];

int main() {
  std::cin >> n >> V;
  memset(f, -0x3f, sizeof(f));
  f[0] = 0, g[0] = 1;
  
  for (int i = 1, v, w; i <= n; ++i) {
    std::cin >> v >> w;
    for (int j = V; j >= v; --j) {
      int mx = std::max(f[j], f[j - v] + w), s = 0;
      if (mx == f[j]) s = g[j];
      if (mx == f[j - v] + w) (s += g[j - v]) %= MOD;
      f[j] = mx, g[j] = s;
    }
  }
 	
  ans = *std::max_element(f, f + V + 1);
  for (int i = 0; i <= V; ++i)
    if (f[i] == ans) cnt += g[i];
  std::cout << cnt << std::endl;
  return 0;
}

背包问题求具体方案

题目描述

有 n 件物品和一个体积为 V​ 的背包。

第 i 件物品体积为 vi，价值为 wi​，每件物品只能用一次。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包体积，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。

状态表示

集合

令 fi, j 表示从后 n − i + 1 件物品中选，总体积不超过 j 的方案集合（至于为什么要这样，见下文）。

属性

集合中的最大价值。

状态转移

容易知道， fi, j ← max {fi + 1, j, fi + 1, j − vi + wi}

初始条件

fn + 1, j = 0 (j ∈ [0, V])

获得方案

题目要求输出 字典序最小的方案。从前往后考虑，每个物品必然是 能选就选。

如何知道第 i​ 个物品能不能选呢？

可以看 fi, j 是否从选第 i 个物品的情况转移过来（如果 fi + 1, j = fi + 1, j − vi + wi，根据能选就选的原则，也得选）

Q：为什么要这样定义 fi, j？

A：倒着定义，f1, V 就是全局最优解。根据转移的情况来向后推，f2, ΔV, f2, ΔV′, ⋯ 都是全局最优解，保证输出结果是全局最优方案。但是如果正着定义，f1, V 是局部最优解，在后面的转移中可能没有入选，会导致输出结果不是全局最优方案。

提供一组数据：

输入

1
2
3
4
5
4 5
1 2
2 4
3 4
4 6

输出 1（倒着定义）

1
1 4

输出 2（正着定义）

1
1 2

可以发现输出 2 只是纯粹的能选就选，没有考虑全局情况。

（这里可能解释不清楚，轻喷/kk）

详见代码。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
const int N = 1e3 + 10; // 假设 n,V 同阶

int n, V, v[N], w[N], f[N][N]; // 此时不能压成一维了

int main() {
  std::cin >> n >> V;
  for (int i = 1; i <= n; ++i) std::cin >> v[i] >> w[i];
  
  for (int i = n; i; --i)
    for (int j = 0; j <= V; ++j) {
      f[i][j] = f[i + 1][j];
      if (j >= v[i]) f[i][j] = std::max(f[i][j], f[i + 1][j - v[i]] + w[i]);
    }
  
  int j = V; // 剩余空间的体积
  for (int i = 1; i <= n; ++i) {
    if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) { // 从选第 i 个的情况转移过来
      std::cout << i << " ";
      j -= v[i];
    }
  }
  std::cout << std::endl;
  return 0;
}

可达性背包

令 fj 表示体积能否凑到 j。

假设当前枚举到第 i 个位置，则 fj = fj − vi