比如我们先缩小范围,指定5个州,那么50个州也是同样的算法。
states_need = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # 传入一个数组, 它被转换为集合
有的同学可能对这些州没概念,这个简称就跟京代表北京,鲁代表山东,甘代表甘肃一样,细细一看,都是西部的一些州。
如何使用贪心算法呢,就是选择覆盖尽可能多的州的电台,然后逐步缩小范围。那么覆盖面广的州所对应的电台就优先被选中,依次类推。
程序的实现是指定了一个集合states_need,里面包含所有的州,每个电台对应的州是通过初始化的数组元素来实现的,按照一二三四五的顺序来命名,当然实际上这种元素的排列set不是按照数组名的顺序,在这个场景里是kfive,ktwo,kthree,kone,kfour
然后逐步缩小范围来收敛,里面比较特别的一点就是集合的运算,使用了 & ,得到的是交集,如果是并集是 |,差集是 -,
程序代码如下:
#!/usr/bin/env python
# coding:utf-8
states_need = 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"])
print(stations)
# 最终选择的广播台集合
final_stations = set()
while states_need:
best_station = None
states_covered = set()
for station, states_for_station in stations.items():
covered = states_need & states_for_station # 求交集
print("states_need:",states_need,"states_for_station:",states_for_station,"covered:",covered)
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
states_need -= states_covered
final_stations.add(best_station)
print("states_needed:",states_need,"best_station:",best_station,"final_stations:",final_stations)
print("---")
print("Final_stations:",final_stations)
为了方便调试和得到一个迭代的结果,我加了几处输出日志,工参考。
{'kfive': set(['ca', 'az']), 'ktwo': set(['mt', 'id', 'wa']), 'kthree': set(['ca', 'or', 'nv']), 'kone': set(['ut', 'id', 'nv']), 'kfour': set(['ut', 'nv'])}
('states_need:', set(['wa', 'ut', 'ca', 'id', 'mt', 'az', 'or', 'nv']), 'states_for_station:', set(['ca', 'az']), 'covered:', set(['ca', 'az']))
('states_needed:', set(['wa', 'ut', 'id', 'mt', 'or', 'nv']), 'best_station:', 'kfive', 'final_stations:', set(['kfive']))
---
('states_need:', set(['wa', 'ut', 'id', 'mt', 'or', 'nv']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', set(['mt', 'id', 'wa']))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set(['or', 'nv']))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ut', 'id', 'nv']), 'covered:', set(['ut', 'nv']))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ut', 'nv']), 'covered:', set(['ut', 'nv']))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'az']), 'covered:', set([]))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', None, 'final_stations:', set(['ktwo', None, 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', set([]))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', None, 'final_stations:', set(['ktwo', None, 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set(['or', 'nv']))
('states_needed:', set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ut', 'id', 'nv']), 'covered:', set(['ut']))
('states_needed:', set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ut', 'nv']), 'covered:', set(['ut']))
('states_needed:', set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ca', 'az']), 'covered:', set([]))
('states_needed:', set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', set([]))
('states_needed:', set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set([]))
('states_needed:', set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ut', 'id', 'nv']), 'covered:', set(['ut']))
('states_needed:', set([]), 'best_station:', 'kone', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive', 'kone']))
---
('states_need:', set([]), 'states_for_station:', set(['ut', 'nv']), 'covered:', set([]))
('states_needed:', set([]), 'best_station:', 'kone', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive', 'kone']))
---
('Final_stations:', set(['ktwo', 'kthree', None, 'kfive', 'kone']))
最后的结果是:ktwo,kthree,kfive,kone这四个电台。
当然贪心算法得到的不是精确的结果,即可能不是最优解,算是一种近似算法,能够基本得到的最优解,而且效率很高。