给定1个1000行×20列的0-1矩阵,对于该矩阵的任意1列,其中值为1的元素的数量不超过10%。设有两个非空集合A和B,每个集合由矩阵的若干列组成。集合A和B互斥是指对于矩阵的任意一行,同时满足下列2个条件:1)若A中有一个或多个元素在这一行上的值是1,则B中的元素在这一行全部是0;2)若B中有一个或多个元素在这一行上的值是1,则A中的元素在这一行全部是0。请你设计一个算法,找出一对互斥集合A和B,使得A和B包含的列的总数最大。
2条回答 默认 最新
- bobhuang 2019-11-12 17:17关注
讲个思路:
由于集合为任意列的组合,总共20列,所以用二进制位来表示比较方便计算。可以用32位整数来表示一个集合。
题设的条件,从一个角度来理解,即每行或者A或者B,必须有一个全0的列组成的集合;对应的,另外一个集合是任意的,可以全0,可以含有1。对第i行来说,先分出为0的列的集合,记为C[i].
初始时,A和B均为全集。
对后续的每个i = [0 ~ 999],有两种选择:
1. 这行选择A为全0,新的A取A和C[i]的交集,计算为 A = A & C[i], B不变。
2. 这行选择B为全0, 新的B取B和C[i]的交集,计算为 B = B & C[i], A不变。
用一个大小1000的数组记录当前每行的选择。如果此时A或B出现空集,则组合失败,回溯到上一个i。
如果到达最后一个i=999,且A和B都不为空,则得到一个有效解。
遍历完所有可能之后,取所有有效解中A和B的列总数最大的那个,作为最优解。特别的,对全是0的行,不需要进行计算。
总的可能空间比较恐怖,有2的1000次方,但是计算中有几个优化计算的方法:
1. 对全0的优化。
2. 出现空集的优化。
3. 当A和B的列数小于等于当前有效解时,不可能更有,也可以优化。最终计算时间可能不会很长。
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 7无用
悬赏问题
- ¥15 如何在scanpy上做差异基因和通路富集?
- ¥20 关于#硬件工程#的问题,请各位专家解答!
- ¥15 关于#matlab#的问题:期望的系统闭环传递函数为G(s)=wn^2/s^2+2¢wn+wn^2阻尼系数¢=0.707,使系统具有较小的超调量
- ¥15 FLUENT如何实现在堆积颗粒的上表面加载高斯热源
- ¥30 截图中的mathematics程序转换成matlab
- ¥15 动力学代码报错,维度不匹配
- ¥15 Power query添加列问题
- ¥50 Kubernetes&Fission&Eleasticsearch
- ¥15 報錯:Person is not mapped,如何解決?
- ¥15 c++头文件不能识别CDialog