给定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 vue2(标签-chrome|关键词-浏览器兼容)
- ¥15 python网络流自动生成系统 医学领域
- ¥15 sql查询仓库里都有什么
- ¥15 代码的修改,添加和运行完善
- ¥15 krpano-场景分组和自定义地图分组
- ¥15 lammps Gpu加速出错
- ¥15 关于PLUS模型中kapaa值的问题
- ¥15 关于博途V17进行仿真时无法建立连接问题
- ¥15 机器学习教材中的例题询问
- ¥15 求.net core 几款免费的pdf编辑器