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'}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python 正则表达式贪婪模式与非贪婪模式原理、用法实例分析

    本文实例讲述了python 正则表达式贪婪模式与非贪婪模式原理.用法.分享给大家供大家参考,具体如下: 之前未接触过正则表达式,今日看python网络爬虫的源码,里面一行正则表达式匹配的代码初看之下,不是很理解,代码如下: myItems = re.findall('<div.*?class="content".*?title="(.*?)">(.*?)</div>',unicodePage,re.S) ".*?"这种匹配

  • 在Python中实现贪婪排名算法的教程

    在较早的一遍文章中,我曾经提到过我已经写了一个属于自己的排序算法,并且认为需要通过一些代码来重新回顾一下这个排序算法. 对于我所完成的工作,我核实并且保证微处理器的安全.对非常复杂的CPU进行测试的一个方法就是创建该芯片的另一个模型,其可以用来产生在CPU上运行的伪随机指令流.这所谓的ISG(指令流产生器)能够在很短的时间内创建几千(甚至几百万)个这样的测试,通过某种方式,使其可以巧妙地给出一些对将在CPU上执行的指令流的控制或操纵. 现在对这些指令流进行模拟,可以通过每一个测试实例花费的时间获

  • Python正则表达式教程之三：贪婪/非贪婪特性

    之前已经简单介绍了Python正则表达式的基础与捕获,那么在这一篇文章里,我将总结一下正则表达式的贪婪/非贪婪特性. 贪婪 默认情况下,正则表达式将进行贪婪匹配.所谓"贪婪",其实就是在多种长度的匹配字符串中,选择较长的那一个.例如,如下正则表达式本意是选出人物所说的话,但是却由于"贪婪"特性,出现了匹配不当: >>> sentence = """You said "why?" and I say

  • Python正则表达式非贪婪、多行匹配功能示例

    本文实例讲述了Python正则表达式非贪婪.多行匹配功能.分享给大家供大家参考,具体如下: 一些regular的tips: 1 非贪婪flag >>> re.findall(r"a(\d+?)","a23b") # 非贪婪模式 ['2'] >>> re.findall(r"a(\d+)","a23b") ['23'] 注意比较这种情况: >>> re.findall(r&q

  • python贪婪匹配以及多行匹配的实例讲解

    1 非贪婪flag >>> re.findall(r"a(\d+?)", "a23b") ['2'] >>> re.findall(r"a(\d+)", "a23b") ['23'] 注意比较这种情况: >>> re.findall(r"a(\d+)b", "a23b") ['23'] >>> re.findall(

  • python中如何使用正则表达式的非贪婪模式示例

    前言 本文主要给大家介绍了关于python使用正则表达式的非贪婪模式的相关内容,分享出来供大家参考学习,下面话不多说了,来一起详细的介绍吧. 在正则表达式里,什么是正则表达式的贪婪与非贪婪匹配 如:String str="abcaxc"; Patter p="ab*c"; 贪婪匹配:正则表达式一般趋向于最大长度匹配,也就是所谓的贪婪匹配.如上面使用模式p匹配字符串str,结果就是匹配到:abcaxc(ab*c). 非贪婪匹配:就是匹配到结果就好,就少的匹配字符.如上

  • Python使用贪婪算法解决问题

    Python使用贪婪算法解决问题 集合覆盖问题 假设你办了个广播节目,要让全美50个州的听众都收听到.为此,你需要决定在哪些广播台播出.在每个广播台播出都需要支出费用,因此你力图在尽可能少的广播台播出 1.创建一个列表,其中包含要覆盖的州 states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", &q

  • Python实现PDF文字识别提取并写入CSV文件

    Python实现PDF文字识别提取并写入CSV文件

    目录 1.前言 2.需求描述 3.开始动手动脑 3.1安装相关第三方包 3.2导入需要用到的第三方库 3.3读取pdf文件,并识别内容 3.4对识别的数据进行处理,写入csv文件 总结 1. 前言 扫描件一直受大众青睐,任何纸质资料在扫描之后进行存档,想使用时手机就能打开,省心省力.但是扫描件的优点也恰恰造成了它的一个缺点,因为是通过电子设备扫描,所以出来的是图像,如果想要处理文件上的内容,直接操作是无法实现的. 那要是想要引用其中的内容怎么办呢?别担心,Python帮你解决问题. 2. 需求描

  • 中秋送礼分配不均这款python刮刮卡完美解决问题

    中秋送礼分配不均这款python刮刮卡完美解决问题

    导语 每次回家小编的身边都会聚集着一堆小朋友,这就是家住一个村的好处. 一回家就接收到七大姑八大姨的亲切的问候,关系那是特别不错的,小朋友也不怕我. ​ 去年因为给小朋友带了一些礼物但是分配不均匀,导致了灾难现场哭声一片...... 我老妈还以为我咋的她们了? ​ emmmmmm,完了我只想说一句,"打扰了" 今年中秋怕家里的小孩子们因为分配礼物重蹈覆辙,聪明的我制作了一款中秋礼物刮刮乐,刮到什么就拿什么! ​ 正文 中秋送给孩子们的礼物已经选好了,当当当图片如下: ​ 一堆中秋月饼的

  • Python面向对象编程基础解析（一）

    1.什么是面向对象 面向对象(oop)是一种抽象的方法来理解这个世界,世间万物都可以抽象成一个对象,一切事物都是由对象构成的.应用在编程中,是一种开发程序的方法,它将对象作为程序的基本单元. 2.面向对象与面向过程的区别 我们之前已经介绍过面向过程了,面向过程的核心在'过程'二字,过程就是解决问题的步骤,面向过程的方法设计程序就像是在设计一条流水线,是一种机械式的思维方式 优点:复杂的问题简单化,流程化 缺点:扩展性差 主要应用场景有:Linux内核,git,以及http服务 面向对象的程序设计

  • python 如何快速找出两个电子表中数据的差异

    最近刚接触python,找点小任务来练练手,希望自己在实践中不断的锻炼自己解决问题的能力. 公司里会有这样的场景:有一张电子表格的内容由两三个部门或者更多的部门用到,这些员工会在维护这些表格中不定期的跟新一些自己部门的数据,时间久了,大家的数据就开始打架了,非常不利于管理.怎样快速找到两个或者多个电子表格中数据的差异呢? 解决办法: 1. Excel自带的方法(有兴趣的自行百度) 2. python 写一个小脚本 #!/usr/bin/env python # -*- coding: utf-8

  • windows下python之mysqldb模块安装方法

    windows下python之mysqldb模块安装方法

    之所以会写下这篇日志,是因为安装的过程有点虐心.目前这篇文章是针对windows操作系统上的mysqldb的安装.安装python的mysqldb模块,首先当然是找一些官方的网站去下载:https://pypi.python.org/pypi/MySQL-python.下载后,cmd进入MySQL-python-1.2.3文件夹,按常规的执行python setup.py install 命令安装此模块,然后就报错了: 这个报错很明显,print 进行python前,应该先确定当前mysqldb

  • PHP实现的贪婪算法实例

    本文实例讲述了PHP实现的贪婪算法.分享给大家供大家参考,具体如下: 背景介绍:贪婪算法与数据结构知识库算法可以说是离我们生活最近的一种算法,人总是贪婪的嘛,所以这种算法的设计是很符合人性的.之所以这么说,是因为人们会在生活中有意无意的使用贪婪算法来解决问题.最常见的就是找零钱了,每个人都没学过该怎么找零钱,但在所有面额的钱都充足时,每个人都会找出同样组合来凑够需要的钱.其实这里面就是贪婪算法在起作用. 设计思路:贪婪法的设计思路可以从两方面来理解,即直观上和数学上.从直观上理解贪婪算法就是用最

  • Python实现将一个大文件按段落分隔为多个小文件的简单操作方法

    本文实例讲述了Python实现将一个大文件按段落分隔为多个小文件的简单操作方法.分享给大家供大家参考,具体如下: 今天帮同学处理一点语料.语料文件有点大,并且是以连续两个换行符作为段落标志,他想把它按段落分隔成多个小文件,即每3个段落组成一个新文件.由于以前没有遇到过类似的操作,在网上找了一些相似的方法,看起来都有点复杂.所以经尝试,自己写了一段代码,完美解决问题. 基本思路是,先读原文件内容,并使用正则表达式,依据\n\n进行切片处理,结果为一个列表,其中每一个列表元素都存放一个切片中的内容;

  • 不可错过的十本Python好书

    不可错过的十本Python好书

    以往的文章中小编已经给大家陆续推荐了很多的Python书籍,可以说品种齐全.本本经典了,不知道你是不是已经眼花缭乱,不知道该选择哪本好了呢?今天我来为大家分享十本不可错过的Python好书,分别适合入门.进阶到精深三个不同阶段的人来阅读. Python高性能编程 Amazon 五星畅销书. Python 入门进阶必读. Python代码仅仅能够正确运行还不够,你需要让它运行得更快. Python核心编程(第3版) (点击图书,可直接下载) 系列销量逾70000册. Python高手进阶图书,详解

  • Python的Flask框架中SQLAlchemy使用时的乱码问题解决

    一.问题 这两天在学习使用flask + SQLAlchemy 定制一个web查询页面的demo ,在测试时,发现查询到的结果显示乱码 .这里将解决方法记录下. 二.解决思路 1.flask 程序上定位 flask的文档中提到可以通过设置SQLALCHEMY_NATIVE_UNICODE来禁止使用SQLAlchemy默认的Unicode编码.有可能是SQLAlchemy默认的Unicode编码不是UTF-8,抱着这样的想法,在程序中指定了"SQLALCHEMY_NATIVE_UNICODE=Fa

随机推荐