求AB互斥集合

求AB互斥集合

求AB互斥集合

/讲个思路:

由于集合为任意列的组合,总共20列,所以用二进制位来表示比较方便计算。可以用32位整数来表示一个集合。

题设的条件,从一个角度来理解,即每行或者A或者B,必须有一个全0的列组成的集合;对应的,另外一个集合是任意的,可以全0,可以含有1。

对第i行来说,先分出为0的列的集合,记为C[i].

初始时,A和B均为全集。

对后续的每个i = [0 ~ 999],有两种选择:

这行选择A为全0,新的A取A和C[i]的交集,计算为 A = A & C[i], B不变。这行选择B为全0, 新的B取B和C[i]的交集,计算为 B = B & C[i], A不变。

用一个大小1000的数组记录当前每行的选择。

如果此时A或B出现空集,则组合失败,回溯到上一个i。

如果到达最后一个i=999,且A和B都不为空,则得到一个有效解。

遍历完所有可能之后,取所有有效解中A和B的列总数最大的那个,作为最优解。

特别的,对全是0的行,不需要进行计算。

总的可能空间比较恐怖,有2的1000次方,但是计算中有几个优化计算的方法:

对全0的优化。出现空集的优化。当A和B的列数小于等于当前有效解时,不可能更有,也可以优化。

最终计算时间可能不会很长。

相关推荐

外交之王郦食其,如何死于韩信的内卷?
俄罗斯世界杯终究躲不过政治色彩干预
哪个奇迹私服变态版本最耐玩?2025年玩家实测推荐