1020. 潜水员

多维费用 01 背包。

背包问题中，根据题目的问题来定义状态表示和进行状态初始化。

问题 状态定义
求最大值 花费不超过
求方案数 花费恰好为
求最小值 花费至少为
  1. 如果题目问最大值，对于不合法状态就设置成负无穷，在取 max 的时候会被丢弃；
  2. 如果题目问最小值，对于不合法状态就设置成正无穷，在取 min 的时候会被丢弃；
  3. 如果题目问方案数，对于不合法状态就设置成 0，在累加时不会有任何方案数贡献；

这道题 f(i,j,k)f(i, j, k) 表示：所有从前 i 个物品中选，氧气量至少为 j，氮气量至少为 k 的选法的气缸重量最小值。

初始条件 f(0,0,0)=0f(0, 0, 0) = 0，从含义出发：从前 0 个物品中选（说明一个也不选），氧气量至少为 0，氮气量至少为 0 的选法的气缸重量最小值，显然是 0。

其他 f(0,j,k)f(0, j, k) 不合法，从含义出发：从前 0 个物品中选（说明一个也不选），氧气量至少为 j，氮气量至少为 k 的选法的气缸重量最小值，显然这样的状态不合法，因为一个气缸都不选，氧气量和氮气量不可能存在。为了不使用这些非法状态，我们将它们设置成正无穷，在取 min 操作的时候会被丢弃。

潜水员 DP 分析

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 <cstring>
#include <iostream>
using namespace std;

const int N = 80, M = 22;

int n, m, k;
int f[M][N];

int main() {
  cin >> m >> n >> k;
  memset(f, 0x3f, sizeof f);
  f[0][0] = 0;
  while (k--) {
    int v1, v2, w;
    cin >> v1 >> v2 >> w;
    for (int j = m; j >= 0; j--) {
      for (int k = n; k >= 0; k--) {
        f[j][k] = min(f[j][k], f[max(0, j - v1)][max(0, k - v2)] + w);
      }
    }
  }
  cout << f[m][n] << endl;
  return 0;
}

12. 背包问题求具体方案

如果要求具体方案就不能压缩成一维空间了。这道题要输出最佳方案中字典序最小的。需要依次考虑第一个物品选不选、第二个物品选不选，直到第 N 个，如果第一个物品能选就一定选，因为 1 x x 一定比不选 1 的 2 x x 字典序要小，这样贪心法来求。

为了求具体方案需要从 dp 数组倒推，那么我们 dp 时，用 f[i][j] 表示：所有从 i ~ n 物品中选，总体积不超过 j 的选法，值是物品价值最大值。所以状态转移方程为：f[i][j] = max(f[i+1][j], f[i+1][j-v[i]] + w[i])。最终 f[1][m] 存储的是答案，求具体方案时，从 f[1][m] 开始依次判断当前状态是从哪个状态转移过来的。也就是看 f[i][j] = f[i+1][j] 还是 f[i][j] = f[i+1][j-v[i]] + w[i]，当初做的决策是什么。如果 f[i][j] = f[i+1][j] = f[i+1][j-v[i]] + w[i]，为了使字典序最小，我们必须选当前物品 i，然后再从 f[i+1][j-v[i]] 继续推。

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
31
32
33
#include <iostream>
using namespace std;

const int N = 1010;
int f[N][N];
int v[N], w[N];
int n, m;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
  for (int i = n; i; i--) {
    for (int j = 0; j <= m; j++) {
      f[i][j] = f[i + 1][j];
      if (j >= v[i]) {
        f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
      }
    }
  }
  // f[1][m] 是最大值，从这里开始倒推，是从哪个状态转移过来的
  int i = 1, j = m;
  // 从 1 开始，依次看物品 i 能不能选
  while (i <= n) {
    if (j >= v[i] && f[i + 1][j - v[i]] + w[i] >= f[i + 1][j]) {
      cout << i << ' ';
      j -= v[i];
      i++;
    } else {
      i++;
    }
  }
  return 0;
}

1013. 机器分配

分组背包。

每个公司看成一组物品。给公司分配 1 台机器还是 2 台机器还是 M 个机器，看成一组物品中的 M 个物品，体积分别是 1、2 … M ，价值由题目输入的矩阵给出。

机器分配背包转化

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;

const int N = 20;
int f[N][N];
int w[N][N];
int way[N];
int n, m;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> w[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {  // 组号 i
    for (int j = 0; j <= m; j++) {
      for (int k = 0; k <= m; k++) {  // 组内物品编号 k
        if (j >= k) {
          f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
        }
      }
    }
  }
  cout << f[n][m] << endl;
  // 从 f[n][m] 往前倒推
  int j = m;
  for (int i = n; i; i--) {
    for (int k = 0; k <= j; k++) {
      // 判断当前 f[i][j] 是从哪里转移过来的
      if (f[i][j] == f[i - 1][j - k] + w[i][k]) {
        // 记录下这个决策
        way[i] = k;
        // 再从 f[i-1][j-k] 继续往前推
        j -= k;
        break;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << i << ' ' << way[i] << endl;
  }
  return 0;
}

487. 金明的预算方案

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#define v first
#define w second

using namespace std;

typedef pair<int, int> PII;

const int N = 70, M = 32010;

int n, m;
int f[M];
PII master[N]; // N 是编号，那一组物品
vector<PII> servant[N];

int main() {
  cin >> m >> n;
  for (int i = 1; i <= n; i++) {
    int v, w, q;
    cin >> v >> w >> q;
    if (!q) {
      // 当前物品是主件
      master[i] = {v, v * w};
    } else {
      servant[q].push_back({v, v * w});
    }
  }
  // 枚举每组物品
  for (int i = 1; i <= n; i++) {
    if (master[i].v) {
      // 枚举背包容量
      for (int j = m; j >= 0; j--) {
        // 用二进制的方式枚举每组物品中主件和附件的选择方案
        for (int k = 0; k < 1 << servant[i].size(); k++) {
          int v = master[i].v, w = master[i].w;
          for (int u = 0; u < servant[i].size(); u++) {
            if (k >> u & 1) {
              v += servant[i][u].v;
              w += servant[i][u].w;
            }
          }
          if (j >= v) f[j] = max(f[j], f[j - v] + w);
        }
      }
    }
  }
  cout << f[m] << endl;
  return 0;
}