【算法图解】——集合覆盖问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法图解】——集合覆盖问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1293字，纯文字阅读大概需要2分钟。

内容图文

文章目录

• 集合覆盖问题
• 州集合，电台字典
• 电台选择

集合覆盖问题

• 覆盖问题要求不会重复——采用set（）
• 假设你要办一个广播电台，要让所有的8个州都听到，你要选择广播电台，如何选择尽可能少的广播电台
  
  
  

州集合，电台字典

# 包含所有州的集合
states_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az']) # 州不会出现重复

# 广播电台字典
stations = {}
stations["kone"] = set(['id', 'nv', 'ut'])
stations['ktwo'] = set(['wa', 'id', 'mt'])
stations['kthree'] = set(['or', 'nv', 'ca'])
stations['kfour'] = set(['nv', 'ut'])
stations['kfive'] = set(['ca', 'az'])

# 最终选择的电台
final_stations = set()

电台选择

• 以需要覆盖的州为循环条件
• 每一次魂循环找出覆盖州最多的电台

# 反复循环直到需要的州变成0，以需要覆盖的州为循环条件
while states_needed:
    # 遍历电台，从中选择覆盖了最多的未覆盖的广播电台
    best_station = None
    states_covered = set()
    
    # 找到电台中能包含需要州最多的那个电台
    for station, states_for_station in stations.items():
        covered = states_needed & states_for_station
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered

    final_stations.add(best_station) # 最佳电台放到最终选择电台的集合中

    # 更新需要的州
    states_needed -= states_covered
    
print(final_stations)

{‘kthree’, ‘ktwo’, ‘kfive’, ‘kone’}

• 点赞
• 收藏
• 分享
• • 文章举报

我是小杨我就这样 发布了182 篇原创文章 · 获赞 45 · 访问量 1万+ 私信 关注

内容总结

以上是互联网集市为您收集整理的【算法图解】——集合覆盖问题全部内容，希望文章能够帮你解决【算法图解】——集合覆盖问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---