美文网首页
贪婪算法

贪婪算法

作者: SingleDiego | 来源:发表于2018-12-14 15:42 被阅读10次

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

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

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

{
    '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)

相关文章

  • 代码小工蚁的#《算法图解》#学习笔记-C8贪婪算法

    代码小工蚁的#《算法图解》#学习笔记-C8贪婪算法C8 贪婪算法greedy algorithms 一、贪婪算法 ...

  • 贪婪、分治、回溯和动态规划,四种算法的比较

    贪婪算法 贪婪算法,也被称为“贪心算法”。贪婪算法分阶段地工作。在每一个阶段,都可以认为所作决定是好的,而不考虑将...

  • 读书笔记

    读书笔记/人生算法之无知、衰朽和贪婪 【标题】人生算法之无知、衰朽和贪婪 【书籍】人生算法 【01】人生算法之无知...

  • 贪婪算法

    1.贪婪算法: 每一步都采用当前局部的(这里是重点)最优的做法,最终得到全局最优解;这是一种完美算法,要找到最优的...

  • 贪婪算法

    3.集合覆盖问题 现在有个广播节目,需要让全美50个州的听众收听。每个广播台都覆盖特定的区域,不同广播台覆盖区域可...

  • 贪婪算法

    1.教室调度问题 一间教室的课程表如上所示,现在如果尽可能在这个教室上最多的课,需要怎么安排课程呢?由于课程之间有...

  • 贪婪算法

    贪婪算法(Greedy Algorithm)也叫算贪心法,贪婪法.它是一个遵循启发式解决问题的算法范式.它的核心思...

  • 贪婪算法

    贪婪算法:选择局部最优解达到全局最优 区间调度问题 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不...

  • 贪婪算法

    假设某节目要覆盖以下省份: 各个电视台的覆盖范围如下: 解决思路: step1: 选出一个覆盖了最多未覆盖省份的电...

  • 贪婪算法

    在求解一个问题的过程中,每次选择都是当前最优解(即局部最优解,而非全局最优解) 贪婪算法使用场景:1,遇到NP完全...

网友评论

      本文标题:贪婪算法

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