Python实现的贪婪算法分析

符号 阅读:205 2020-02-19 11:32:35 评论:0
# 使用Python实现贪婪算法
# 集合覆盖问题
# 假设你办了个广播节目,要让全美50个州的听众都收听到。为此,你需要决定在哪些广播台播出。在每个广播台播出都需要支出费用,因此你力图在尽可能少的广播台播出
# 1.创建一个列表,其中包含要覆盖的州
states_needed =
set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
# 2.使用散列表表示可供选择的广播台清单
stations =
dict() 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"])
# 3.使用集合来存储最终选择的广播台
final_stations =
set()
# 5.循环
while states_needed:
# 遍历所有的广播台,从中选择覆盖最多的未覆盖州的广播台,将这个广播台存储在best_station
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) # 结果为{'ktwo', 'kthree', 'kone', 'kfive'}
标签:Python
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

扫一扫关注我们,了解最新精彩内容