Python使用贪婪算法解决问题
作者:水滴月 时间:2022-04-13 10:23:14
Python使用贪婪算法解决问题
集合覆盖问题
假设你办了个广播节目,要让全美50个州的听众都收听到。为此,你需要决定在哪些广播台播出。在每个广播台播出都需要支出费用,因此你力图在尽可能少的广播台播出
1.创建一个列表,其中包含要覆盖的州
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
2.使用散列表表示可供选择的广播台清单
stations = dict() 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"])
3.使用集合来存储最终选择的广播台
final_stations = set()
4.循环
while states_needed:
# 遍历所有的广播台,从中选择覆盖最多的未覆盖州的广播台,将这个广播台存储在best_station中
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)
print(final_stations) # 结果为{'ktwo', 'kthree', 'kone', 'kfive'}
来源:https://www.cnblogs.com/lty-fly/p/11713955.html
标签:python,贪婪,算法
0
投稿
猜你喜欢
python中Task封装协程的知识点总结
2022-10-25 13:25:02
详解SQL Server分布式查询
2010-09-19 09:07:00
vue学习笔记之动态组件和v-once指令简单示例
2024-01-01 07:50:52
python代码实现烟花实例
2022-09-13 18:09:18
appium+python adb常用命令分享
2022-12-27 09:16:24
Python操作Jira库常用方法解析
2022-02-06 01:56:11
python 绘制场景热力图的示例
2022-01-22 07:03:21
python借助ChatGPT读取.env实现文件配置隔离保障私有数据安全
2022-12-26 17:54:13
用javascript实现页面无刷新更新数据
2011-08-14 07:54:08
在JavaScript中,为什么要尽可能使用局部变量?
2009-03-01 12:38:00
asp压缩access数据库(带密码)方法
2007-09-06 19:48:00
Facebook开源一站式服务python时序利器Kats详解
2023-11-13 18:29:13
Python标准库之typing的用法(类型标注)
2021-09-27 01:25:24
Web2.0视觉风格进化论 之二
2007-11-03 20:10:00
详解PHP中的mb_detect_encoding函数使用方法
2023-11-14 19:48:45
JavaScript程序执行顺序问题总结
2010-01-29 13:06:00
OpenCV 图像梯度的实现方法
2023-07-14 08:25:43
ASP关于SQL插入数据后获得当前ID
2010-01-24 19:55:00
asp如何判断偶数和奇数?
2010-01-12 20:16:00
在ASP中使用SQL语句之5:开始执行
2007-08-11 12:36:00