二进制集合与状压 DP

二进制集合

二进制集合介绍

利用计算机存储数据的特点，我们可以用二进制数来表示集合。

设一个集合有 n 个元素，则可以使用一个 n bit 的数来表示该集合的所有子集，若该数字第 k 个 bit 位为 1，表示存在该元素，为 0 则说明不存在该元素。

例如，有集合：\(U = \{0, 1, 2, 3\}\)，则 1111 表示全集 \(U\)，0000 表示空集 \(\emptyset\)，1010 表示子集 \(\{1, 3\}\)。

一般情况下，若要表示的集合元素数量较少，可以直接使用 int 或者 long long 整数来表示，若集合元素的数量大于 64，则可以考虑使用 C++ 中的 std::bitset 来表示，可以参考笔者之前的文章：std::bitset 讲解 。

二进制集合的运算

设有集合 \(A\) 和 \(B\) ，它们的二进制表示分别为 a 和 b ，则常见的集合运算规则如下：

一元运算 数学表示 二进制集合表示
集合的阶 \(|A|\) __builtin_popcount(a)（a 为 int 类）
__builtin_popcountll(a) （a 为 long long 类）
a.count() （a 为 std::bitset 类）
补集 \(\overline{A}\) ~a
二元运算 数学表示 二进制集合表示
集合并 \(A \cup B\) a | b
集合交 \(A \cap B\) a & b
集合差 \(A - B\) a & ~b

二进制集合子集的遍历

若集合 \(X\) 的二进制表示为 x ，则逆序遍历 \(X\) 的非空子集的代码如下：

1
2
3
for (auto sub = x; sub; sub = (sub - 1) & x) {
    // s 为 x 的子集
}

状态压缩 DP

状态压缩 DP 是一种在动态规划算法中使用的优化技巧。它主要应用于具有指数级别状态数的问题，通过将状态用一个整数表示，从而减少内存空间的使用和提高计算效率。这里所说的用一个整数表示状态，也就是上文提到的二进制集合。

典型示例

状压 + 图论

Shortest Path Visiting All Nodes

我们设 \(dp[i][S]\) 表示从顶点 \(i\) 出发，需要走完集合 \(S\) 包含的所有点的最小步数，不难得到状态转移方程： \[ dp[i][S] = \underset{<i, j> \in G(V, E)}{\text{min}}\ dp[j][S - i] + 1 \] 基于此，我们可以用记忆化搜索来解决问题。但由于这里面是可以走回路的，则可能出现无限递归的情况，为了解决这个问题，我们可以在递归函数中对状态 \((i, S)\) 进行标记（代码中是将 \(dp[i][S]\) 设置为一个特殊的值），保证每个状态只经过一次，这个做法显然是合理的，因为如果从顶点 \(i\) 出发，走了若干步回到顶点 \(i\) 后，需要走完的点的集合还是 \(S\)，则说明这若干步都没有意义，顾可以舍去。

递归出口： \[ dp[i][S] = 0\ \ \text{if}\ S = \{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
class Solution {
private:
    int dp[12][1 << 12]; // dp[i][s], 起点为 i, 需要走完集合 s 所有点的最短路径
    static const int inf = 0x3f3f3f3f;
public:
    Solution() {
        memset(dp, 0xff, sizeof(dp));
    }

    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        function<int(int, int)> dfs = [&](int i, int s) -> int {
            int& res = dp[i][s];
            if (res >= 0) return res;
            res = -2; // 后续不再处理 dfs(i, s), 避免无限递归
            s &= ~(1 << i);
            if (s == 0) return res = 0;
            int ans = inf;
            for (int j : graph[i]) {
                if (dp[j][s] != -2) ans = min(ans, dfs(j, s) + 1);
            }

            return res = ans;
        };

        int res = inf;
        for (int i = 0; i < n; i++) res = min(res, dfs(i, (1 << n) - 1));

        return res;
    }
};
状压 + 背包

Number of Ways to Wear Different Hats to Each Other

这道题是背包问题与状态压缩的结合，我们设 \(dp[i][S]\) 表示可以使用前 \(i\) 个帽子，分配人员集合为 \(S\) 的方案数。

对于 \(dp[i][S]\)，若 \(i > 0\) 且 \(S\) 非空，则可以分两种情况讨论：

  1. 所有人都不戴 \(\text{hat}_i\) ，一共有 \(dp[i - 1][S]\) 种方案
  2. 有一个人戴 \(\text{hat}_i\) ，则我们从集合 \(S\) 中选择一个喜欢 \(\text{hat}_i\) 的人 \(j\) 让他戴上这个帽子，找出所有符合条件的人，一共有 \(\sum_j dp[i - 1][S - j]\) 种方案

将以上二者求和即可，基于此，我们可以得到状态转移方程： \[ \begin{equation} dp[i][S] = \left\{ \begin{array}{ll} \ \ dp[i - 1][S] + \sum_{j \in S \land i \in \text{hats}[j]} dp[i - 1][S - j] & \text{if}\ \ S \not= \emptyset\ \ \text{and}\ \ i > 0 \\ \ \ 1 & \text{if}\ \ S = \emptyset \\ \ \ 0 & \text{if}\ \ |S| > i \end{array} \right. \end{equation} \] 代码如下：

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
class Solution {
private:
    using i64 = long long;
    static const int MOD = 1e9 + 7;
    int dp[41][1 << 10]; // dp[i][S] 表示可以使用前 i 个帽子，需要分配的人员集合为 S 的方案数
public:
    Solution() {
        memset(dp, 0x00, sizeof(dp));
    }

    int numberWays(vector<vector<int>>& hats) {
        int n = hats.size();
        vector<i64> pref(n, 0ll);
        for (int i = 0; i < n; i++) {
            for (int j : hats[i]) pref[i] |= (1ll << j); // 记录每个人的喜好
        }
        for (int i = 1; i <= 40; i++) {
            dp[i - 1][0] = 1;
            for (int mask = 1, sz = (1 << n); mask < sz; mask++) {
                if (__builtin_popcountll(mask) > i) continue;
                dp[i][mask] = dp[i - 1][mask]; // 不选择 hat_i
                // 选择 hat_i
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) && (pref[j] & (1ll << i))) {
                        // 从当前的人员集合中找到喜欢 hat_i 的人
                        dp[i][mask] = ((i64)dp[i][mask] + dp[i - 1][mask ^ (1 << j)]) % MOD;
                    }
                }
            }
        }

        return dp[40][(1 << n) - 1];
    }
};

由于 \(dp[i][:]\) 只与 \(dp[i - 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
28
29
30
31
32
class Solution {
private:
    using i64 = long long;
    static const int MOD = 1e9 + 7;
    int dp[1 << 10]; // 滚动数组优化空间
public:
    Solution() {
        memset(dp, 0x00, sizeof(dp));
    }

    int numberWays(vector<vector<int>>& hats) {
        int n = hats.size();
        vector<i64> pref(n, 0ll);
        for (int i = 0; i < n; i++) {
            for (int j : hats[i]) pref[i] |= (1ll << j); // 记录每个人的喜好
        }
        dp[0] = 1;
        for (int i = 1; i <= 40; i++) {
            for (int mask = (1 << n) - 1; mask; mask--) {
                if (__builtin_popcountll(mask) > i) continue;
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) && (pref[j] & (1ll << i))) {
                        // 从当前人员集合中找到喜欢 hat_i 的人
                        dp[mask] = ((i64)dp[mask] + dp[mask ^ (1 << j)]) % MOD;
                    }
                }
            }
        }

        return dp[(1 << n) - 1];
    }
};
其他

这里给出其他的案例链接和笔者提供的 AC 代码，如果读者感兴趣可以自行尝试去完成。

Maximize Score After N Operations

参考代码：

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
class Solution {
private:
    int gcd(int x, int y) {
        return x ? gcd (y % x, x) : y;
    }
    int g_map[14][14]; // 提前记录 gcd(i, j)
    int dp[1 << 14]; // dp[S] 表示当前剩余点的集合为 S 可以拿到的最大得分
public:
    Solution() {
        memset(g_map, 0x00, sizeof(g_map));
        memset(dp, 0xff, sizeof(dp));
        dp[0] = 0;
    }

    int maxScore(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                g_map[i][j] = g_map[j][i] = gcd(nums[i], nums[j]);
            }
        }
        function<int(int)> dfs = [&](int mask) -> int {
            if (dp[mask] != -1) return dp[mask];
            int idx = 1 + (n - __builtin_popcount(mask)) / 2; // 当前游戏次数
            vector<int> sub;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) sub.push_back(i);
            }
            int res = 0;
            for (int i = 0, sz = sub.size(); i < sz - 1; i++) {
                for (int j = i + 1; j < sz; j++) {
                    int x = sub[i], y = sub[j];
                    res = max(res, idx * g_map[x][y] + dfs(mask ^ (1 << x) ^ (1 << y)));
                }
            }

            return dp[mask] = res;
        };

        return dfs((1 << n) - 1);
    }
};

总结

状态压缩动态规划并不是在 DP 算法本身上创新，而是给某个维度为「集合」的状态提供了一种利于计算机运算的表达方式。什么时候考虑使用状压 DP 呢？

  1. 动态规划中的状态转移涉及到集合运算（交、并、补、差）
  2. 集合的最大阶是一个比较小的数字，即 \(2 ^ {|S|}\) 是计算机内存可以承受的数组大小

这种情况下，就很有可能是一个状压 DP 的问题了。

数据结构与算法
#C++ #位运算 #集合
二进制集合与状压 DP
https://goer17.github.io/2023/06/28/二进制集合与状压 DP/
作者
Captain_Lee
发布于
2023年6月28日
许可协议