怎么使用Python贪心算法解决集合覆盖问题

本文小编为大家详细介绍“怎么使用python贪心算法解决集合覆盖问题”，内容详细，步骤清晰，细节处理妥当，希望这篇“怎么使用Python贪心算法解决集合覆盖问题”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

在《算法图解》里面有一个蛮有意思的小案例，背景是一个广播节目，要让全美的50个周的听众都能够听到，但是每个电台可能覆盖多个州，每在一个电台播出就需要一笔费用，所以就是从成本的角度来看，怎么尽可能在所有的州都播出，这是一个典型的集合覆盖的问题，而且在我们的生活中算是比较典型。

比如我们先缩小范围，指定5个州，那么50个州也是同样的算法。

states_need = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # 传入一个数组， 它被转换为集合

有的同学可能对这些州没概念，这个简称就跟京代表北京，鲁代表山东，甘代表甘肃一样，细细一看，都是西部的一些州。

如何使用贪心算法呢，就是选择覆盖尽可能多的州的电台，然后逐步缩小范围。那么覆盖面广的州所对应的电台就优先被选中，依次类推。

程序的实现是指定了一个集合states_need，里面包含所有的州，每个电台对应的州是通过初始化的数组元素来实现的，按照一二三四五的顺序来命名，当然实际上这种元素的排列set不是按照数组名的顺序，在这个场景里是kfive,ktwo,kthree,kone,kfour

然后逐步缩小范围来收敛，里面比较特别的一点就是集合的运算，使用了 & ,得到的是交集，如果是并集是 |，差集是 -，

程序代码如下：

#!/usr/bin/env python# coding:utf-8states_need = 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"])print(stations)# 最终选择的广播台集合final_stations = set()while states_need:best_station = Nonestates_covered = set()for station, states_for_station in stations.items():covered = states_need & states_for_station # 求交集print("states_need:",states_need,"states_for_station:",states_for_station,"covered:",covered)if len(covered) > len(states_covered):best_station = stationstates_covered = coveredstates_need -= states_coveredfinal_stations.add(best_station)print("states_needed:",states_need,"best_station:",best_station,"final_stations:",final_stations)print("---")print("Final_stations:",final_stations)

为了方便调试和得到一个迭代的结果，我加了几处输出日志，工参考。

{'kfive': set(['ca', 'az']), 'ktwo': set(['mt', 'id', 'wa']), 'kthree': set(['ca', 'or', 'nv']), 'kone': set(['ut', 'id', 'nv']), 'kfour': set(['ut', 'nv'])}('states_need:', set(['wa', 'ut', 'ca', 'id', 'mt', 'az', 'or', 'nv']), 'states_for_station:', set(['ca', 'az']), 'covered:', set(['ca', 'az']))('states_needed:', set(['wa', 'ut', 'id', 'mt', 'or', 'nv']), 'best_station:', 'kfive', 'final_stations:', set(['kfive']))---('states_need:', set(['wa', 'ut', 'id', 'mt', 'or', 'nv']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', set(['mt', 'id', 'wa']))('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set(['or', 'nv']))('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ut', 'id', 'nv']), 'covered:', set(['ut', 'nv']))('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ut', 'nv']), 'covered:', set(['ut', 'nv']))('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'az']), 'covered:', set([]))('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', None, 'final_stations:', set(['ktwo', None, 'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', set([]))('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', None, 'final_stations:', set(['ktwo', None, 'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set(['or', 'nv']))('states_needed:', set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))---('states_need:', set(['ut']), 'states_for_station:', set(['ut', 'id', 'nv']), 'covered:', set(['ut']))('states_needed:', set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))---('states_need:', set(['ut']), 'states_for_station:', set(['ut', 'nv']), 'covered:', set(['ut']))('states_needed:', set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))---('states_need:', set(['ut']), 'states_for_station:', set(['ca', 'az']), 'covered:', set([]))('states_needed:', set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))---('states_need:', set(['ut']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', set([]))('states_needed:', set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))---('states_need:', set(['ut']), 'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set([]))('states_needed:', set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))---('states_need:', set(['ut']), 'states_for_station:', set(['ut', 'id', 'nv']), 'covered:', set(['ut']))('states_needed:', set([]), 'best_station:', 'kone', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive', 'kone']))---('states_need:', set([]), 'states_for_station:', set(['ut', 'nv']), 'covered:', set([]))('states_needed:', set([]), 'best_station:', 'kone', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive', 'kone']))---('Final_stations:', set(['ktwo', 'kthree', None, 'kfive', 'kone']))

最后的结果是：ktwo,kthree,kfive,kone这四个电台。

读到这里，这篇“怎么使用Python贪心算法解决集合覆盖问题”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注编程网Python频道。