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)單明了！?。?br />
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Matplotlib是一個(gè)強(qiáng)大的Python繪圖庫(kù),可以用來繪制各種靜態(tài)、動(dòng)態(tài)和交互式的圖表,文章介紹了Matplotlib的基本概念、繪制折線圖、散點(diǎn)圖、柱狀圖、直方圖和餅圖等方法,并詳細(xì)解釋了Matplotlib的三層結(jié)構(gòu)2025-02-02
Python-Tkinter Text輸入內(nèi)容在界面顯示的實(shí)例
今天小編就為大家分享一篇Python-Tkinter Text輸入內(nèi)容在界面顯示的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-07-07
在Python中使用PIL模塊對(duì)圖片進(jìn)行高斯模糊處理的教程
這篇文章主要介紹了在Python中使用PIL模塊對(duì)圖片進(jìn)行高斯模糊處理的教程,這個(gè)無圖形界面的腳本代碼非常簡(jiǎn)單,需要的朋友可以參考下2015-05-05
python3獲取當(dāng)前文件的上一級(jí)目錄實(shí)例
下面小編就為大家分享一篇python3獲取當(dāng)前文件的上一級(jí)目錄實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-04-04
本文介紹了threading 模塊提供的線程同步原語包括：Lock、RLock、Condition、Event、Semaphore等對(duì)象。對(duì)大家的學(xué)習(xí)具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友可以參考下2018-10-10
今天小編就為大家分享一篇pandas取出重復(fù)數(shù)據(jù)的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-07-07
利用python實(shí)現(xiàn)終身免費(fèi)的聽書工具
本文通過實(shí)際案例,詳細(xì)介紹了作者如何利用Python庫(kù)實(shí)現(xiàn)文本轉(zhuǎn)語音的過程,從安裝庫(kù)到實(shí)際操作案例,都有詳細(xì)的說明,為讀者提供了一定的參考價(jià)值2024-03-03
Python 批量讀取文件中指定字符的實(shí)現(xiàn)
這篇文章主要介紹了Python 批量讀取文件中指定字符的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
Python統(tǒng)計(jì)時(shí)間內(nèi)的并發(fā)數(shù)代碼實(shí)例
這篇文章主要介紹了Python統(tǒng)計(jì)時(shí)間內(nèi)的并發(fā)數(shù)代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-12-12
更改Python的pip install 默認(rèn)安裝依賴路徑方法詳解
今天小編就為大家分享一篇更改Python的pip install 默認(rèn)安裝依賴路徑方法詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-10-10