greedy算法(python版)

greedy算法的核心思想是首先计算覆盖面大的部分,然后依次寻找其他覆盖面最大的部分。该算法的使用场景就像他的名字一样,当符合贪婪属性的时候就可以考虑。

states_needed = set(['北京', '上海', '广州', '深圳', '杭州', '南京', '石家庄', '银川'])

stations = {}
stations['kone'] = set(['北京', '上海', '广州'])
stations['ktwo'] = set(['北京''杭州', '南京'])
stations['kthree'] = set(['广州', '深圳', '杭州'])
stations['kfour'] = set(['北京', '银川'])
stations['kfive'] = set(['石家庄', '银川'])

final_stations = set()

while states_needed:
    best_station = None
    states_covered = set()
    for station, states in stations.items():
        covered = states_needed & states
        if len(covered) > len(states_covered):
                best_station = station
                states_covered = covered

    states_needed -= states_covered
    final_stations.add(best_station)

print(final_stations)

Original: https://www.cnblogs.com/machao/p/7874420.html
Author: 马在路上
Title: greedy算法(python版)

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/6668/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部
最近整理资源【免费获取】:   👉 程序员最新必读书单  | 👏 互联网各方向面试题下载 | ✌️计算机核心资源汇总