问题描述：
假设你办了个广播节目，要让全美50个洲的听众都能听到，为此，你需要决定在哪些广播台播出，在每个广播台播出都需要支付费用，力图以最少的费用达到覆盖的目的——来自算法图解
贪婪思路：1：找出所有广播台中覆盖面积最广的（面积指的是未覆盖的面积） 换言之就是寻找覆盖未覆盖面积最广的广播站
2：记录本轮的覆盖区域 更新未覆盖区域（取交集 用到集合set）
3：重复 1 2 直至完全覆盖
初始信息：state_needed(需要覆盖的州)，stations 字典（每个广播台覆盖的州）fianl_stations(保存最终选择的广播台)
state_needed=set(['mt','wa','or','id','nv','ut','ca','az']) stations={} stations['1']=set(['id','nv','ut']) stations['2']=set(['wa','id','mt']) stations['3']=set(['or','nv','ca']) stations['4']=set(['nv','ut']) stations['5']=set(['ca','az']) final_stations=set() def find_covermost(): ans,res=0,'' for k,v in stations.items(): if ans<len(v&state_needed) and k not in final_stations:ans,res=len(v),k#v&state_needed很关键，覆盖面积广指的是覆盖还没覆盖的面积最广 final_stations.update([res]) return stations[res] while state_needed: state_needed-=find_covermost() print(final_stations) print(state_needed) ##输出{'5', '3', '1', '2'} #set()
总结：贪婪算法是一种近似算法，通过寻找局部最优解获得全局最优解
前面学到的BFS与狄克斯特拉算法就包含的贪婪的思想
另外今天学到了集合中的两个操作 并集>>& 添加元素>>set.update([seq])
