贪婪算法 python实现（未注释） 21.10.3

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( )



while states_needed:
    best_cover = set( )
    best_station = None
    for station,state_station in stations.items():
        cover=states_needed & state_station
        if len(cover)>len(best_cover):
            best_cover=cover
            best_station=station
    final_stations.add(best_station)
    states_needed-=best_cover
print(final_stations)

集合，列表，字典属于可变数据类型，其余不可变，也就是使用函数改变时，实际上不能被改变

做成函数的报错点：states_needed-=best_cover

经测试，可以做任何操作除了这个，因为左值问题！所以加一个globe就行

第二版：

def serach():
    global states_needed
    while states_needed:
        best_cover = set( )
        best_station = None
        for station,state_station in stations.items():
            cover=states_needed & state_station
            if len(cover)>len(best_cover):
                best_cover=cover
                best_station=station
        final_stations.add(best_station)
        states_needed-=best_cover
    print(final_stations)