Python使用贪婪算法解决问题
作者:水滴月 发布时间:2022-04-13 10:23:14
标签:python,贪婪,算法
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
0
投稿
猜你喜欢
- 考察对于知识的理解,除了实际的代码运用,还有一种方法就是问答类的题型。不同于普通的概念叙述,小编认为即使是面试题也会带有一些数学题目的影响,
- PHP 异常处理异常用于在指定的错误发生时改变脚本的正常流程。异常是什么异常处理用于在指定的错误(异常)情况发生时改变脚本的正常流程。这种情
- 阅读上一篇:你是真正的用户体验设计者吗? Ⅵ很可怕,是吧!图中翻译:(从内到外)第一层:用户体验第二层:内容管理界面设计顾客关系管理交互设计
- 常量:用于储存一个不会变化也不希望变化的数据的标示符(命名规则与变量相同)定义形式:使用 define() 函数定义使用形式:define(
- turtle(海龟)是Python重要的标准库之一,它能够进行基本的图形绘制。turtle图形绘制的概念诞生于1969年,成功应用于LOGO
- 本文实例讲述了js+ajax实现获取文件大小的方法。分享给大家供大家参考,具体如下:顾名思义,通过JS和Ajax来获取上传文件的大小,在上传
- 【错误原因】:mysql_query执行超时.【解决办法】:修改php.ini中的 max_execution_time的值,默认为300,
- 本文实例讲述了php防止sql注入中过滤分页参数的方法。分享给大家供大家参考。具体分析如下:就网络安全而言,在网络上不要相信任何输入信息,对
- 通常我们用 Python 绘制的都是二维平面图,但有时也需要绘制三维场景图,比如像下面这样的:这些图怎么做出来呢?今天就来分享下如何一步步绘
- 1、pyqtgraph库数据可视化效果还不错,特别是窗体程序中图像交互性较好;安装也很方便,用 pip 安装。2、在Python中新建一个
- Javascript 正常取来源网页的URL只要用: document.referrer就可以了!但,如果来源页是Jav
- 异常详细信息: System.Web.HttpException: 无法向会话状态服务器发出会话状态请求。请确保已启动 ASP.NET St
- 本文实例讲述了CentOS 6/7环境下通过yum安装php7的方法。分享给大家供大家参考,具体如下:安装php7已经是现在linux服务器
- 通过XML使系统之间的数据交换变得更简单,因为它与编程语言无关,刚引入XML的概念时,是通过一个脚本或应用程序解析XML数据,将其转换为适合
- pytorch定义新的自动求导函数在pytorch中想自定义求导函数,通过实现torch.autograd.Function并重写forwa
- jieba库是一款优秀的 Python 第三方中文分词库,jieba 支持三种分词模式:精确模式、全模式和搜索引擎模式,下面是三种模式的特点
- 如何在线压缩Access数据库?Access数据库可以在线压缩吗?可以的,代码和说明见下:compact.asp<%option&nb
- MySQL的本地备份和双机相互备份脚本:首先,我们需要修改脚本进行必要的配置,然后以root用户执行。◆1. 第一执行远程备份时先用 fir
- 这些年来,我发现许多开发者对于何时使用数据操纵语言(DML)触发器与何时使用约束感到迷惑。许多时候,如果没有正确应用这两个对象,就会造成问题
- 如何在SQL中启用全文检索功能?本文将通过实例向你剖折这个问题。这是一个全文索引的一个例子,首先在查询分析器中使用:use pubsgo--