Ereshki's Blog

Appearance

背包问题 ​

动态规划 ​

动态规划问题的思考方式：

  • 状态表示 f(i,j)
    • 代表的集合是什么，一般来说会加一些关于 i,j 的限制条件，比如前 i 个物品，总容量不超过 j 等等
    • 表示的是集合的哪个属性，常见的有 最大值/最小值，元素数量
    • 状态表示往往可以维数优化，但一般参照 转移方程 来优化，推荐一开始写全面些
  • 状态计算方法
    • 集合划分：将当前状态如何划分为更小的子结构，同时这些子结构都可以被计算出来
    • 子结构到当前状态的过程就是转移方程
    • 例如 f(i,j) 可以按照是否取第 i 件物品进行划分（注意，划分 最好不重，一定不漏）
  • 注意初始化

01 背包 ​

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

  • 状态表示：f[i][j] 表示只取前 i 个物品，背包总容量不超过 j 的最大价值
  • 集合划分：是否取第 i 个物品
    • 不取：f[i - 1][j]
    • 取：f[i - 1][j - v[i]] + w[i]
    • 这两个子结构的最大值取 max 即可
  • 注意初始化，f[0][0~m] = 0

核心代码：

cpp
for (int i = 1; i <= n; 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]);
        }
    }
}
  • 二重循环，第一重枚举物品，第二重枚举容量大小
  • 两个子结构，注意第二个只有 容量足够大 才可行

AC2. 01 背包问题

显然，f[i][j] 构成了一个矩阵图，动态规划不过就是按图打表罢了，打表的方向为 从左到右，从上到下。同时我们注意到转移方程中 f[i][j] 仅与上一行中的 f[i - 1][j] 和 f[i - 1][j - v[i]] 有关，一个在其正上方，一个在其 左上方。

因此我们将其压缩到一维，删除第一维，这样 f[j] 就会直接覆盖旧值。然而，由于打表的方向是从左到右，因此左上方的 f[i - 1][j - v[i]] 在 f[i][j] 更新之前就已经被更新为了 f[i][j - v[i + 1]]。为了避免这种情况发生，我们可以采取从右往左打表的方式。

从右往左的打表方式自然是没有问题的，因为我们只要在更新本行时，提前准备好上一行的数据即可，无论以什么顺序更新本行都无所谓。这里由于子结构都在左上方，故采取从右往左的更新方式（正上方的恰好用自己的旧值，左上方的用本行中左边尚未更新的值即可）。

AC2. 01 背包问题-一维优化

核心代码：

cpp
for (int i = 1; i <= n; i ++) {
    for (int j = m; j >= 0; j --) {
        if (j >= v[i]) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
}

这里面的 if 甚至可以优化掉：

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

TODO：滚动数组继续优化

完全背包 ​

有 N 件物品和一个容量是 V 的背包。每种物品都有无限件可用。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

  • 状态表示：f[i][j] 表示只取前 i 个物品，背包总容量不超过 j 的最大价值
  • 集合划分：取多少个第 i 个物品分成很多类
    • 选 0 个：f[i - 1][j]
    • 选 1 个：f[i - 1][j - v[i]] + w[i]
    • ...
    • 选 k 个：f[i - 1][j - v[i] * k] + w[i] * k
    • 其中 (k+1) * v[i] > j，多选一个就超了
    • 这些子结构的取 max 即可
  • 注意初始化，f[0][0~m] = 0

注意，直接这样写二维方程，时间复杂度较高，三重循环 O(n3)

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

就算优化为一维，也只是降低了空间复杂度，并没有降低时间复杂度。因此要考虑如何优化掉这个三重循环。

展开这个转移方程：

cpp
f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, f[i-1][j-3v]+3w, ...)
f[i][j-v] = max(         f[i-1][j-v],   f[i-1][j-2v]+w,  f[i-1][j-3v]+2w, ...)

f[i][j] = max(f[i-1][j], f[i][j-v]+w)

可以看出 f[i][j] 中取了第 j 个物品的 所有子结构 可以用 f[i][j-v] + w 完全替换（每一项都差个 w，所有项的最大值自然也在这其中，因此最大值也相差一个 w）。

我们试图直观理解 f[i][j-v] + w 的含义：它表示只在前 i 个物品中做选择时，一定会选择至少一件第 i 个物品，然后剩下的空间再分配给其他物品，可以是第 i 个物品，也可以是其他。

因此我们将集合划分为以下两类：对于第 i 件物品而言

  • f[i][j]：在前 i 件物品中任意选择，背包容量为 j
  • 一件第 i 件物品都不拿：f[i-1][j]
  • 至少拿一件第 i 件物品：f[i][j-v] + w，剩下还是前 i 件物品中任意选择，背包容量缩小到 j−v

于是在二维表格中，f[i][j] 会用到它正上方的 f[i-1][j] 和同一行左边的 f[i][j-v] + w，因此如果我们想降维到一维的话，搜索顺序要保持从左到右，确保左边的 f[i][j-v] + w 更新后才轮到 f[i][j]。

二维核心代码：

cpp
for (int i = 1; i <= n; 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][j - v[i]] + w[i]);
        }
    }
}

一维核心代码：

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

时间复杂度降低到了 O(n2)。

AC3. 完全背包问题

多重背包 ​

有 N 件物品和一个容量是 V 的背包。第 i 件物品的体积是 vi，价值是 wi，最多有 si 件。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

  • 状态表示：f[i][j] 表示只取前 i 个物品，背包总容量不超过 j 的最大价值
  • 集合划分：是否取第 i 个物品
    • 选 0 个：f[i - 1][j]
    • 选 1 个：f[i - 1][j - v[i]] + w[i]
    • ...
    • 选 si 个：f[i - 1][j - v[i] * k] + w[i] * s[i]
    • 其中 (k+1) * v[i] > j，多选一个就超了
    • 这些子结构的取 max 即可
  • 注意初始化，f[0][0~m] = 0
cpp
for (int i = 1; i <= n; i ++) {
    for (int j = 0; j <= m; j ++) {
        for (int k = 0; k <= s[i] && k * v[i] <= j; k ++) {
            f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
        }
    }
}

AC4. 多重背包问题 I

当数据范围变成 N=1000 时，由于三重循环 O(n3)=109 一定会超时。

而我们回顾完全背包问题中 f[i][j-v] + w 的含义：它表示只在前 i 个物品中做选择时，一定会选择至少一件第 i 个物品，然后剩下的空间再分配给其他物品，可以是第 i 个物品（注意在多重背包问题，若 si=1，则这里无法成立），也可以是其他。

cpp
f(i,j) = Max(f(i-1,j), f(i-1,j-v)+w, f(i-1,j-2v)+2w, ..., f(i-1,j-sv)+sw)
f(i,j-v) = Max(        f(i-1,j-v),   f(i-1,j-2v)+w, ...,  f(i-1,j-sv)+(s-1)w, f(i-1,j-(s+1)v)+sw)

考虑二进制优化方式：

  • 假设某个物品有 1023 个，难道我们真的要枚举 1023 次呢？
  • 那么我们可以将 s 分为 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 一共十组，也就是打包
  • 显然 0~1023 中的任何一个数都可以由上述这些数表示，直接转为二进制即可
    • 其他进制是否可以？不可以，因为 1023 的二进制表示中 0 表示不选这个打包，1 表示选择这个打包
    • 经典的 1, 2, 5, 10, 20, 50 是否可以？不可以，例如 9 = 5 + 2 + 2 就不行
  • 对于 s = 200 而言：
    • 首先将其拆分为 1, 2, 4, 8, 16, 32, 64, 200-127 这么多物品
    • 1, 2, 4, 8, 16, 32, 64 可以表示 0 ~ 127
    • 而 128 ~ 200 首先可以必选一个 73，剩下的 55 ~ 127 依然可以用 1, 2, 4, 8, 16, 32, 64 表示
  • 也就是将 S 拆分为 log⁡s 的新物品，对新物品做 01 背包即可，也就是一共有 Nlog⁡S 件物品
  • 总的时间复杂度为 O(VNlog⁡S)≈2×107

核心代码：

cpp
// ...
    for (int i = 1; i <= n; i ++) {
        int a, b, s;
        cin >> a >> b >> s;

        int k = 1;
        while (k <= s) {
            idx ++;

            v[idx] = a * k;
            w[idx] = b * k;

            s -= k;
            k *= 2;
        }

        if (s > 0) {
            idx ++;

            v[idx] = a * s;
            w[idx] = b * s;
        }
    }

AC5. 多重背包问题 II

分组背包问题 ​

有 N 组物品和一个容量是 V 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。si 第 i 组物品一共有多少个物品。

  • 状态表示：f[i][j] 表示只从前 i 组中选物品，背包总容量不超过 j 的最大价值
  • 集合划分：是否取第 i 组中的物品
    • 不选组内物品：f[i - 1][j]
    • 选第 1 个物品：f[i - 1][j - v[i][1]] + w[i][1]
    • ...
    • 选第 si 个物品：f[i - 1][j - v[i][s[i]]] + w[i][s[i]]
    • 注意要保证 v[i][k] <= j
    • 这些子结构的取 max 即可
  • 注意初始化，f[0][0~m] = 0

AC9. 分组背包问题

还是和多重背包一样，选 si 个和第 sj 差不多，都是 O(n3)。

Released under the MIT License.

Copyright © 2024-present Ereshki