Python使用贪婪算法解决问题

yipeiwu_com6年前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'} 

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

python+selenium实现QQ邮箱自动发送功能

python+selenium实现QQ邮箱自动发送功能

python实现从登录到自动发送qq邮件,供大家参考,具体内容如下 qq邮箱登录注意问题 账户密码登录框是写在一个iframe上的,所以我们要先进入iframe中才能定位到下面的两个输入...

Scrapy使用的基本流程与实例讲解

Scrapy使用的基本流程与实例讲解

前面已经介绍过如何创建scrapy的项目,和对项目中的文件功能的基本介绍。 这次,就来谈谈使用的基本流程: (1)首先第一点,打开终端,找到自己想要把scrapy工程创建的路径。这里,我...

python 垃圾收集机制的实例详解

 python 垃圾收集机制的实例详解 pythonn垃圾收集方面的内容如果要细讲还是挺多的,这里只是做一个大概的概括 Python最主要和绝大多数时候用的都是引用计数,每一个...

python射线法判断检测点是否位于区域外接矩形内

本文实例为大家分享了python射线法判断点是否位于区域内的具体代码,供大家参考,具体内容如下 #!/usr/bin/env python # -*- coding: utf-8 -...

Python实现的彩票机选器实例

Python实现的彩票机选器实例

本文实例讲述了Python实现彩票机选器的方法。分享给大家供大家参考。具体实现方法如下: # -*- coding: utf8 -*- from Tkinter import * i...