python基于遞歸解決背包問題詳解
遞歸是個(gè)好東西，任何具有遞歸性質(zhì)的問題通過函數(shù)遞歸調(diào)用會(huì)變得很簡(jiǎn)單。一個(gè)很復(fù)雜的問題，幾行代碼就能搞定。
最簡(jiǎn)單的遞歸問題：現(xiàn)有重量為weight的包，有若干重量分別為W1,W2.....Wn的物品，試問能否從物品中選出若干件而且重量剛好為weight?
weight具體是怎么構(gòu)成的，有下面兩種情況（假設(shè)挑選到Wn時(shí)，剛好夠weight)：
1. 從Wn-1開始就已經(jīng)夠weight，那weight=W1+W2+......+Wn=W1+W2+......+Wn-1.
2.加上Wn后剛好夠weight,那自然地有weight=W1+W2+......+Wn.
上面兩種情況一個(gè)有解，那問題就有解，于是我們可以把Wi從背包去掉倒退回去看weight的值。
經(jīng)過一系列倒推，weight的值有下面三種情況：
1. weight剛剛等于0 //說明有解
2. weight<0 //不可能，所以無解
3. weight>0 and 沒有W了 // 也不可能，無解
def knap(weight,weights,n): //weight為包的容量，weights是一個(gè)所有重量的表，n為重量數(shù)量
if weight==0:
return True;
if weight<0 or (n<1 and weight>0):
return False;
if knap(weight-weights[n-1],weights,n-1): //情況 2
print(weights[n-1])
return True
if knap(weight,weights,n-1): //情況 1
return True
else:
return False
超級(jí)簡(jiǎn)單吧?。?！如果采用動(dòng)態(tài)規(guī)劃解決，幾十行代碼要吧。這就12行代碼，簡(jiǎn)單明了！??！
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
用python wxpy管理微信公眾號(hào)并利用微信獲取自己的開源數(shù)據(jù)
這篇文章主要介紹了用python wxpy管理微信公眾號(hào)并利用微信獲取自己的開源數(shù)據(jù),本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-07-07
巧用python和libnmapd,提取Nmap掃描結(jié)果
本文將會(huì)講述一系列如何使用一行代碼解析 nmap 掃描結(jié)果，其中會(huì)在 Python 環(huán)境中使用到 libnmap 里的 NmapParser 庫(kù)，這個(gè)庫(kù)可以很容易的幫助我們解析 nmap 的掃描結(jié)果2016-08-08
這篇文章主要介紹了Python隊(duì)列、進(jìn)程間通信、線程,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-10-10
PyCharm連接遠(yuǎn)程服務(wù)器配置的全過程
這篇文章主要介紹了PyCharm連接遠(yuǎn)程服務(wù)器配置的全過程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-06-06
實(shí)例解析Python設(shè)計(jì)模式編程之橋接模式的運(yùn)用
這篇文章主要介紹了Python設(shè)計(jì)模式編程之橋接模式的運(yùn)用,橋接模式主張把抽象部分與它的實(shí)現(xiàn)部分分離,需要的朋友可以參考下2016-03-03
這篇文章主要介紹了OpenCV基本操作之邊緣檢測(cè)，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
Python操作Mongodb數(shù)據(jù)庫(kù)的方法小結(jié)
這篇文章主要介紹了Python操作Mongodb數(shù)據(jù)庫(kù)的方法,結(jié)合實(shí)例形式總結(jié)分析了Python針對(duì)MongoDB數(shù)據(jù)庫(kù)的基本模塊導(dǎo)入、連接、增刪改查及排序等相關(guān)操作技巧,需要的朋友可以參考下2019-09-09
這篇文章主要介紹了Python通過遞歸遍歷出集合中所有元素的方法,實(shí)例分析了Python遍歷集合元素的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-02-02
使用LibTorch進(jìn)行C++調(diào)用pytorch模型方式
這篇文章主要介紹了使用LibTorch進(jìn)行C++調(diào)用pytorch模型方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-12-12
這篇文章主要介紹了Python中的多線程,線程就是進(jìn)程中一條執(zhí)行程序的執(zhí)行路徑，一個(gè)程序至少有一條執(zhí)行路徑，本文給大家介紹的非常詳細(xì)，需要的朋友可以參考下2022-06-06