数据结构与算法 / 系统课时
枚举子集完成集合状态转移
枚举子集完成集合状态转移
很多集合 DP 的一个状态并不是从“删掉一个元素”转移,而是要把当前集合拆成两个部分,并尝试所有子集。逐个扫描 0..mask 会浪费大量无效候选,本节用 (sub - 1) & mask 只枚举 mask 的真实子集,并解释总复杂度为何常写成 。
学习目标
- 掌握非空子集的标准位运算枚举写法。
- 理解
(sub - 1) & mask为什么能跳到下一个子集。 - 推导“外层枚举集合、内层枚举子集”出现 的原因,并判断规模是否可接受。
只枚举当前集合真正拥有的子集
假设 mask = 0b10110,其中只有第 1、2、4 位可被选入子集。一个简单但低效的办法是遍历 0..mask,再判断候选是否满足 sub & mask == sub。这样会检查许多包含非法位的整数。
标准写法从 sub = mask 开始,每次执行 sub = (sub - 1) & mask。sub - 1 会改变当前低位结构,而再与 mask 做按位与,会清除所有不属于原集合的位。于是得到的始终是 mask 的子集,而且不会重复。
def submasks(mask):
result = []
sub = mask
# 循环内只产生非空子集;空集可在循环后单独处理。
while sub:
result.append(sub)
sub = (sub - 1) & mask
return result
mask = 0b10110
for sub in submasks(mask):
print(f"{sub:05b}")预期输出
10110
10100
10010
10000
00110
00100
00010这里 mask 含有 3 个有效元素,因此非空子集恰好有 个。若转移必须包含空集,可以在循环结束后额外处理 sub = 0,不要把循环条件直接改成永真,否则会在 0 处重复。
把子集枚举放进 DP 转移
集合拆分型 DP 常见的抽象形式是 dp[mask] = min(dp[mask ^ sub] + cost[sub])。其中 sub 表示从 mask 中拿出的一组元素,mask ^ sub 是剩余部分。由于 sub 保证属于 mask,这里异或与“从集合中删除这些元素”效果一致。
下面是片段示例,依赖已经初始化好的 dp、cost 和当前状态变量 mask:
sub = mask
while sub:
rest = mask ^ sub
dp[mask] = min(dp[mask], dp[rest] + cost[sub])
sub = (sub - 1) & mask这类写法常用于分组、集合划分、选择若干元素一次处理等问题。是否允许 sub = mask、是否允许空集,以及两个部分是否有顺序,都必须根据题意决定,不能机械套公式。
为什么总复杂度是三的幂
只看一个固定 mask,若它有 k 个元素,需要枚举 个子集。但如果外层还要遍历所有 mask,不能简单写成 ,因为小集合的子集数远少于 。
从单个元素的归属看,在一对 (mask, sub) 中它只有三种合法状态:
| 元素状态 | 是否在 mask |
是否在 sub |
|---|---|---|
| 不属于当前集合 | 否 | 否 |
属于 mask 但不属于 sub |
是 | 否 |
同时属于 mask 和 sub |
是 | 是 |
每个元素独立有 3 种选择,因此全部 (mask, sub) 组合总数是 。这也说明“枚举所有集合,再枚举其所有子集”的典型复杂度是 。如果每次转移内部还做额外的 工作,总复杂度还要再乘相应因子。
先用元素规模判断能不能做
增长很快。n = 15 时约有 1430 万个 (mask, sub) 组合,经过常数优化后通常仍有机会;n = 20 时已经超过 34 亿,纯粹的全量枚举通常不可接受。
所以看到“对子集再枚举子集”时,应先检查约束,再决定是否需要减少状态、限制候选子集、预计算有效集合,或者换成别的转移方式。
子集枚举的价值在于把候选空间限制在真实可用的集合上。掌握 (sub - 1) & mask 后,更重要的是先算清楚它被调用多少次:位运算常数很小,但指数级状态数量仍然决定算法能处理的上限。