假设你办了个广播节目，要让全美50个州的听众都收听得到。为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。
每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。
如何找出覆盖全美50个州的最小广播台集合呢？听起来很容易，但其实非常难。具体方法如下。
(1) 列出每个可能的广播台集合，这被称为幂集（power set） 。可能的子集有2n个。
(2) 在这些集合中，选出覆盖全美50个州的最小集合。
问题是计算每个可能的广播台子集需要很长时间。由于可能的集合有2n个，因此运行时间为O(2n)。如果广播台不多，只有5～10个，这是可行的。但如果广播台很多，结果将如何呢？随着广播台的增多，需要的时间将激增。假设你每秒可计算10个子集，所需的时间将如下。
近似算法
贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。
- 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。
- 重复第一步，直到覆盖了所有的州。
这是一种近似算法（approximation algorithm） 。在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：
- 速度有多快；
- 得到的近似解与最优解的接近程度。
贪婪算法是不错的选择，它们不仅简单，而且通常运行速度很快。在这个例子中，贪婪算法的运行时间为O(n^2)，其中n为广播台数量。
下面来看看解决这个问题的代码。
1. 准备工作
出于简化考虑，这里假设要覆盖的州没有那么多，广播台也没有那么多。
首先，创建一个列表，其中包含要覆盖的州。
states_needed = set(["mt", "wa", "or", "id", "nv", "ut","ca", "az"])
# 你传入一个数组，它被转换为集合
我使用集合来表示要覆盖的州。集合类似于列表，只是同样的元素只能出现一次，即集合不能包含重复的元素。例如，假设你有如下列表。
>>> arr = [1, 2, 2, 3, 3, 3]
并且你将其转换为集合。
>>> set(arr)
set([1, 2, 3])
在这个集合中， 1、 2和3都只出现一次。
还需要有可供选择的广播台清单，我选择使用散列表来表示它。
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"])
其中的键为广播台的名称，值为广播台覆盖的州。在该示例中，广播台kone覆盖了爱达荷州、内达华州和犹他州。所有的值都是集合。你马上将看到，使用集合来表示一切可以简化工作。
最后，需要使用一个集合来存储最终选择的广播台。
final_stations = set()
2. 计算答案
接下来需要计算要使用哪些广播台。根据右边的示意图，你能确定应使用哪些广播台吗？
正确的解可能有多个。你需要遍历所有的广播台，从中选择覆盖了最多的未覆盖州的广播台。我将这个广播台存储在best_station中。
best_station = None
states_covered = set()
for station, states_for_station in stations.items():
states_covered是一个集合，包含该广播台覆盖的所有未覆盖的州。 for循环迭代每个广播台，并确定它是否是最佳的广播台。下面来看看这个for循环的循环体。
covered = states_needed & states_for_station #你没见过的语法！它计算交集
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
其中有一行代码看起来很有趣。
covered = states_needed & states_for_station
它是做什么的呢？
3. 集合
假设你有一个水果集合。
还有一个蔬菜集合。
有这两个集合后，你就可以使用它们来做些有趣的事情。
下面是你可以对集合执行的一些操作。
- 并集意味着将集合合并。
- 交集意味着找出两个集合中都有的元素（在这里，只有西红柿符合条件）。
- 差集意味着将从一个集合中剔除出现在另一个集合中的元素。
下面是一个例子。
>>> fruits = set(["avocado", "tomato", "banana"])
>>> vegetables = set(["beets", "carrots", "tomato"])
>>> fruits | vegetables #并集
set(["avocado", "beets", "carrots", "tomato", "banana"])
>>> fruits & vegetables #交集
set(["tomato"])
>>> fruits – vegetables #差集
set(["avocado", "banana"])
>>> vegetables – fruits #你觉得这行代码是做什么的呢？
这里小结一下：
- 集合类似于列表，只是不能包含重复的元素；
- 你可执行一些有趣的集合运算，如并集、交集和差集。
4. 回到代码
回到前面的示例。
下面的代码计算交集。
covered = states_needed & states_for_station
covered 是一个集合 ， 包含同时出现在states_needed 和states_for_station中的州；
换言之，它包含当前广播台覆盖的一系列还未覆盖的州！接下来，你检查该广播台覆盖的州是否比best_station多。
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
如果是这样的，就将best_station设置为当前广播台。最后，你在for循环结束后将best_station添加到最终的广播台列表中。
final_stations.add(best_station)
你还需更新states_needed。由于该广播台覆盖了一些州，因此不用再覆盖这些州。
states_needed -= states_covered
你不断地循环，直到states_needed为空。这个循环的完整代码如下。
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)
最后，你打印final_stations，结果类似于下面这样。
>>> print final_stations
set(['ktwo', 'kthree', 'kone', 'kfive'])
结果符合你的预期吗？选择的广播台可能是2、 3、 4和5，而不是预期的1、 2、 3和5。下面来比较一下贪婪算法和精确算法的运行时间。
