贪婪算法

假设某节目要覆盖以下省份：

["广东", "广西", "海南", "福建", "湖南", "江西", "贵州", "云南"]

各个电视台的覆盖范围如下：

{
    'TV1': {'湖南', '江西', '福建'},
    'TV2': {'广西', '福建', '广东'}, 
    'TV3': {'湖南', '海南', '贵州'}, 
    'TV4': {'湖南', '江西'}, 
    'TV5': {'云南', '贵州'}, 
    }

解决思路：

• step1： 选出一个覆盖了最多未覆盖省份的电视台，即使覆盖了已覆盖的省份也没关系

• step2： 重复第一步，直到所有身份被覆盖

python 代码实现如下：

# 需要覆盖的省份
states_needed = set(["广东", "广西", "海南", "福建", "湖南", "江西", "贵州", "云南"])

# 每个电视台能覆盖的省份
stations = {}
stations["TV1"] = set(["福建", "湖南", "江西"])
stations["TV2"] = set(["广西", "福建", "广东"])
stations["TV3"] = set(["海南", "湖南", "贵州"])
stations["TV4"] = set(["湖南", "江西"])
stations["TV5"] = set(["贵州", "云南"])

# 选择合符条件的电视台加到这个集合中
final_stations = set()

# 循环一直运行到所有省份被覆盖
while states_needed:
    best_station = None
    states_covered = set() # 记录已覆盖的省份

    for station, states in stations.items():
        """
        stations 是电视台名
        states 是电视台覆盖范围，数据类型为 set
        """

        # python 的集合运算
        # 得出：电视台覆盖的范围和实际要覆盖的范围的交集
        covered = states_needed & states

        # 找出覆盖省份最多的电视台
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered

    # 把已覆盖的省份从 states_needed 去掉
    states_needed = states_needed - states_covered
    # 把选择的电视台加到 final_stations 中
    final_stations.add(best_station)

print(final_stations)