《算法图解》——贪心算法
# 首先创建一个表，包含所覆盖的州
states_needed = set(['mt','wa','or','id','nv','ut','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()
""" 计算答案 """
#遍历所有广播台，计算覆盖最多未覆盖州的广播台
while states_needed:
best_station = None
states_coverd = set()
for station, states in stations.items():
coverd = states_needed & states # 求交集。
if len(coverd) > len(states_coverd): # coverd 包含在states_needed和states_for_station 中的州。检查该州是否比best_station覆盖的多。
best_station = station
states_coverd = coverd
states_needed -= states_coverd
final_stations.add(best_station) # 如果是就把best_station 设置为当前广播台
print(final_stations)
输出结果：
