给定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 三菱伺服电机按启动按钮有使能但不动作
- ¥20 为什么我写出来的绘图程序是这样的,有没有lao哥改一下
- ¥15 js,页面2返回页面1时定位进入的设备
- ¥200 关于#c++#的问题,请各位专家解答!网站的邀请码
- ¥50 导入文件到网吧的电脑并且在重启之后不会被恢复
- ¥15 (希望可以解决问题)ma和mb文件无法正常打开,打开后是空白,但是有正常内存占用,但可以在打开Maya应用程序后打开场景ma和mb格式。
- ¥15 绘制多分类任务的roc曲线时只画出了一类的roc,其它的auc显示为nan
- ¥20 ML307A在使用AT命令连接EMQX平台的MQTT时被拒绝
- ¥20 腾讯企业邮箱邮件可以恢复么
- ¥15 有人知道怎么将自己的迁移策略布到edgecloudsim上使用吗?