Python使用貪婪算法解決問題
更新時(shí)間：2019年10月22日 11:48:01 作者：水滴月
這篇文章主要介紹了Python使用貪婪算法解決問題,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
Python使用貪婪算法解決問題
集合覆蓋問題
假設(shè)你辦了個(gè)廣播節(jié)目，要讓全美50個(gè)州的聽眾都收聽到。為此，你需要決定在哪些廣播臺播出。在每個(gè)廣播臺播出都需要支出費(fèi)用，因此你力圖在盡可能少的廣播臺播出
1.創(chuàng)建一個(gè)列表，其中包含要覆蓋的州
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.循環(huán)
while states_needed:
# 遍歷所有的廣播臺，從中選擇覆蓋最多的未覆蓋州的廣播臺，將這個(gè)廣播臺存儲在best_station中
best_station = None
# 這個(gè)集合包含該廣播臺覆蓋的所有未覆蓋的州
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'}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了Python如何操作docker redis過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08
python3實(shí)現(xiàn)帶多張圖片、附件的郵件發(fā)送
這篇文章主要為大家詳細(xì)介紹了python3實(shí)現(xiàn)帶多張圖片、附件的郵件發(fā)送，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-08-08
Python順序結(jié)果、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)詳解
這篇文章主要給大家介紹了關(guān)于Python順序結(jié)果、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的相關(guān)資料, 程序由3種基本結(jié)構(gòu)組成,順序結(jié)構(gòu)、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu),需要的朋友可以參考下2023-07-07
利用Python批量壓縮png方法實(shí)例（支持過濾個(gè)別文件與文件夾）
這篇文章主要給大家介紹了關(guān)于利用Python批量壓縮png的相關(guān)資料，文中介紹的方法支持過濾個(gè)別文件與文件夾，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友們下面跟著小編來一起看看吧。2017-07-07
Python數(shù)據(jù)分析23種Pandas核心操作方法總結(jié)
在本文中，作者從基本數(shù)據(jù)集讀寫、數(shù)據(jù)處理和?DataFrame?操作三個(gè)角度展示了?23?個(gè)?Pandas?核心方法，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
這篇文章主要介紹了如何在代碼中安裝Python模塊,本文結(jié)合示例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-06-06
Python 十六進(jìn)制整數(shù)與ASCii編碼字符串相互轉(zhuǎn)換方法
今天小編就為大家分享一篇Python 十六進(jìn)制整數(shù)與ASCii編碼字符串相互轉(zhuǎn)換方法，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
這篇文章主要講解得內(nèi)容是python與js進(jìn)行MD5取hash有什么不同，我們在做前端做滲透測試時(shí)會遇到一些關(guān)鍵字進(jìn)行了加密得情況，而且python和js對json進(jìn)行md5取hash,MD5結(jié)果值還不一致，下面我們就爛看看到底是哪里不同吧，需要的朋友可以參考一下2022-02-02
這篇文章主要介紹了Python如何測試stdout輸出，幫助大家更好的理解和學(xué)習(xí)Python，感興趣的朋友可以了解下2020-08-08
使用Python 統(tǒng)計(jì)高頻字?jǐn)?shù)的方法
今天小編就為大家分享一篇使用Python 統(tǒng)計(jì)高頻字?jǐn)?shù)的方法，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-01-01