アルゴリズム入門——greedy algorithmアルゴリズム、貪欲アルゴリズムpython実現

最小のstationsですべての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"])

states_needed=set(["mt","wa","or","id","nv","ut","ca","az"])
final_station=set()

while states_needed:
    best_station=None
    states_convered=set()
    for station,states in stations.items():#       ，  
        convered=states_needed & states
        if len(convered)>len(states_convered):
            best_station=station
            states_convered=convered
    states_needed-=states_convered
    final_station.add(best_station)