仅用于记录学习，欢迎批评指正，大神勿喷
系列文章目录
《算法图解》总结第 1 章：二分查找、大O表示法；
《算法图解》总结第 2 章：数组和链表，选择排序；
《算法图解》总结第 3 章：while循环、递归、栈；
《算法图解》总结第 4 章：分而治之、快速排序；
《算法图解》总结第 5 章：散列表；
《算法图解》总结第 6 章：广度优先搜索；
《算法图解》总结第 7 章：狄克斯特拉算法；
《算法图解》总结第 8 章：贪婪算法
《算法图解》总结第 9 章：动态规划
《算法图解》总结第 10 章：K最近邻算法
《算法图解》总结第 11 章：十种算法简介
文章目录NP完全问题
贪婪算法
贪婪算法很简单：每步都采取最优的做法，用专业术语来说，就是每步都选择局部最优解，最终得到的就是全局最优解 。（贪婪算法并非在任何情况下都行之有效，第7章乐谱换架子鼓就是一个典型例子 。）
贪婪算法有时不能获得最优解，但是非常接近，有时你只需找到一个能够大致解决问题的算法，此时就可使用贪婪算法，这是一种近似算法 。近似算法判断优劣的标准：
（1）速度有多快；
（2）得到的近似解与最优解的接近程度；
贪婪算法优点：易于实现，运行速度快，是不错的近似算法 。
补充知识
并集、交集、差集
和数学中学的一样，这里作补充的是实现代码（），直接借用例子进行说明 。
案例：
fruits = set(["avocado","tomato","banana"])vegetables = set(["beets","carrots","tomato"])
并集：将集合合并
fruits | vegetables
输出结果：
{'avocado', 'banana', 'beets', 'carrots', 'tomato'}
交集：找出两个集合中都有的元素
fruits & vegetables
输出结果：
{'tomato'}
差集：从一个集合中剔除出现在另一个集合中的元素
fruits - vegetables
输出结果：
{'avocado', 'banana'}
应用案例：集合覆盖问题
案例：假设办个广播节目，要让全美50个州的听众都收听到，为支付较低的费用，尽量选择尽可能少的广播台播出 。以下图为例，每个广播台能覆盖的特定区域，不同广播台的覆盖区域可能重叠 。
将上图整理成表，显示如下：
文章插图
案例分析
第一步：创建一个列表,包含要覆盖的州，要用集合来表示，集合类似于列表，但是集合中不能包含重复的元素
states_needed = 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"])第三步：定义一个集合来存储最终选择的广播台
final_stations = set()第四步：贪婪算法实现
# 只要州还没覆盖完，一直执行while循环while states_needed:# 定义最初最好的广播台best_station = None# 定义一个集合，存储已经覆盖的州states_covered = set()''' for循环迭代每个广播台，并确定它是否是最佳，items()存储键值(广播台和相应的覆盖州)即每次仅能确定一个最佳的广播台'''for station,states_from_station in stations.items():# 需要覆盖的州和当前该广播台能覆盖的州的交集covered = states_needed & states_from_station # 如果当前广播台州交集的个数大于当前要覆盖的州if len(covered) > len(states_covered):# 就替换为最佳的广播台best_station = station# 替换已经覆盖的州states_covered = covered# for循环结束一次后，要从需要覆盖的州中减去已经覆盖过的州states_needed -= states_covered # 打印剩余需要覆盖的州print('states_needed:',states_needed)'''添加最佳的广播台，并开始下一轮新的while循环直至需要覆盖的州为空 （注：新一轮while循环中的best_station和states_covered不是for循环后的，还是while循环中最初定义的那些，因为for循环只是while循环中的一块，这个必须想明白）'''final_stations.add(best_station)print(final_stations)
- 月嫂先生是什么电视剧
- 特警力量是什么电视剧
- 带你快速看完9.8分神作《Effective Java》—— 通用编程篇
- 《思考致富》不应该指望不经历“暂时的失败”便能发财
- 《思考致富》制造借口是一个根深蒂固的习惯
- 《基于OPENPOSE的三维上肢康复系统》论文解读
- 5th Edition 《C++ Primer 》笔记-Part I
- 床是草东的什么歌曲
- 《巨人的陨落》用英文怎么说
- 游戏党福利 《PlayCast》让你手机玩PS4游戏