greedy算法(python版)

作者: 老马的春天 | 来源:发表于2017-11-21 17:35 被阅读37次

    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)   
    
    

    相关文章

      网友评论

        本文标题:greedy算法(python版)

        本文链接:https://www.haomeiwen.com/subject/dobwvxtx.html