侧边栏壁纸
  • 累计撰写 43 篇文章
  • 累计创建 0 个标签
  • 累计收到 32 条评论

目 录CONTENT

文章目录

关于状压DP枚举子集的方法与理解

我们现在要枚举状压集合 SS 的子集,代码实现:

for (int S1=S;S1!=0;S1=(S1-1)&S) {
  S2=S^S1;
}

其中 S1S_1 就是我们枚举得到的子集,S2S_2 是当前子集 S1S_1SS 内的补集,即 S1S2=SS_1 \bigoplus S_2 = S

S2=SS1{\because S_2 = S \bigoplus S_1}

S2S1=SS1S1{\therefore S_2 \bigoplus S_1 = S \bigoplus S_1 \bigoplus S_1}

S2S1=S(S1S1){\therefore S_2 \bigoplus S_1 = S \bigoplus (S_1 \bigoplus S_1)}

S2S1=S0{\therefore S_2 \bigoplus S_1 = S \bigoplus 0}

S2S1=S{\therefore S_2 \bigoplus S_1 = S}

赘述如下

现在来讲一讲为什么是这样的一个枚举方法,先让我们来举一个例子来模拟一下。

假设我们当前要枚举的是 (10110)2(10110)_2 的子集(子集仍然用 S1S_1 表示):

S1=(10110)2(10100)2(10010)2(10000)2(110)2(100)2(10)2S_1 = (10110)_2 \Rightarrow (10100)_2 \Rightarrow (10010)_2 \Rightarrow (10000)_2 \Rightarrow (110)_2 \Rightarrow (100)_2 \Rightarrow (10)_2

根据例子,我们发现按照上面代码得到的结果是正确的,并且是把子集按照从大到小的顺序枚举出来的。那么接下来我们来谈谈这样枚举的正确性。

首先,一个集合它自己本身也是自己的一个集合,所以我们从这个集合本身开始枚举。

既然是枚举,那我们就先考虑把当前枚举得到的子集先 1-1(即 S11S_1 - 1),但是这样做不能保证 1-1 后得到的状态是原状态的子集,但是我们注意到:根据 与运算& 的性质,我们不难发现如果两个数 a, b,a < b,我们对这两个数进行&运算,最后的结果一定是b的子集,因为我们 与运算& 得到的结果,其二进制中所有1出现的位置在b的二进制对应位置也是1。

现在已经说明了这样做确实得到了原集合的一个子集 S1S_1,但是还没有说明我们通过上述方式枚举,可以枚举完原集合 SS 的所有子集。

其实枚举子集就相当于在原集合的二进制状态下把一些1换为0,而我们每次 1-1 然后进行与运算其实就是在把当前子集 S1S_1 的最右边的1的右边全部变为1,自己变为0,然后和集合 SS 进行与运算把新增的1中不该出现的抹去,最后只剩下了原集合中存在的1了。

Preference

0

评论区