# 使用贪心算法解决集合覆盖问题

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

```#!/usr/bin/env python
# coding:utf-8

states_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 = None
states_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 = station
states_covered = covered
states_need -= states_covered
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']))```

1452 篇文章158 人订阅

0 条评论

## 相关文章

### hdu1561（数组dp入门）

ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有...

20810

38550

38660

50090

25250

13640

### 算法导论第九章中位数和顺序统计量（选择问题）

本章如果要归结成一个问题的话，可以归结为选择问题，比如要从一堆数中选择最大的数，或最小的数，或第几小/大的数等， 这样的问题看似很简单，似乎没有什么可研究的...

39470

### 程序员进阶之算法练习（三十）附基础教程

BAT常见的算法面试题解析：程序员算法基础——动态规划程序员算法基础——贪心算法工作闲暇也会有在线分享，算法基础教程-。

25430

31780

34360