Python使用貪婪算法解決問題
更新時(shí)間：2019年10月22日 11:48:01 作者：水滴月
這篇文章主要介紹了Python使用貪婪算法解決問題,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
Python使用貪婪算法解決問題
集合覆蓋問題
假設(shè)你辦了個(gè)廣播節(jié)目，要讓全美50個(gè)州的聽眾都收聽到。為此，你需要決定在哪些廣播臺(tái)播出。在每個(gè)廣播臺(tái)播出都需要支出費(fèi)用，因此你力圖在盡可能少的廣播臺(tái)播出
1.創(chuàng)建一個(gè)列表，其中包含要覆蓋的州
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
2.使用散列表表示可供選擇的廣播臺(tái)清單
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.使用集合來存儲(chǔ)最終選擇的廣播臺(tái)
final_stations = set()
4.循環(huán)
while states_needed:
# 遍歷所有的廣播臺(tái)，從中選擇覆蓋最多的未覆蓋州的廣播臺(tái)，將這個(gè)廣播臺(tái)存儲(chǔ)在best_station中
best_station = None
# 這個(gè)集合包含該廣播臺(tái)覆蓋的所有未覆蓋的州
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) # 結(jié)果為{'ktwo', 'kthree', 'kone', 'kfive'}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Python OpenCV簡(jiǎn)單的繪圖函數(shù)使用教程
本文主要為大家介紹了OpenCV中一些簡(jiǎn)單的繪圖函數(shù)的使用教程，文中的示例代碼講解詳細(xì)，對(duì)我們了解OpenCV有一定的幫助，感興趣的可以學(xué)習(xí)一下2022-01-01
這篇文章主要介紹了win10安裝python的全過程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-09-09
Python實(shí)現(xiàn)驗(yàn)證碼識(shí)別
這篇文章主要介紹了Python實(shí)現(xiàn)驗(yàn)證碼識(shí)別的方法，文中講解非常詳細(xì)，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-06-06
解決python selenium3啟動(dòng)不了firefox的問題
今天小編就為大家分享一篇解決python selenium3啟動(dòng)不了firefox的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-10-10
這篇文章主要介紹了ML神器：sklearn的快速使用及入門，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)大量圖片重命名，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
python實(shí)現(xiàn)猜數(shù)字游戲(無重復(fù)數(shù)字)示例分享
這篇文章主要介紹了python實(shí)現(xiàn)猜數(shù)字游戲(無重復(fù)數(shù)字)示例,需要的朋友可以參考下2014-03-03
在本文中，我們將介紹 Python 中 _ 字符的不同用法。就像 Python 中的許多其他內(nèi)容一樣，我們會(huì)看到 “_” 的不同用法主要是慣例問題。這里我們將介紹幾種不同的情況。2020-10-10
Python解決非線性規(guī)劃中經(jīng)濟(jì)調(diào)度問題
Scipy是Python算法庫(kù)和數(shù)學(xué)工具包，包括最優(yōu)化、線性代數(shù)、積分、插值、特殊函數(shù)、傅里葉變換等模塊。scipy.optimize模塊中提供了多個(gè)用于非線性規(guī)劃問題的方法，適用于不同類型的問題。本文將利用起解決經(jīng)濟(jì)調(diào)度問題，感興趣的可以了解一下2022-05-05
今天小編就為大家分享一篇python在每個(gè)字符后添加空格的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-05-05