python基于遞歸如何解決背包問題

這篇文章主要介紹了python基于遞歸如何解決背包問題，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

遞歸是個好東西，任何具有遞歸性質(zhì)的問題通過函數(shù)遞歸調(diào)用會變得很簡單。一個很復(fù)雜的問題，幾行代碼就能搞定。

  最簡單的遞歸問題：現(xiàn)有重量為weight的包，有若干重量分別為W1,W2.....Wn的物品，試問能否從物品中選出若干件而且重量剛好為weight?

  weight具體是怎么構(gòu)成的，有下面兩種情況（假設(shè)挑選到Wn時，剛好夠weight)：

  1. 從Wn-1開始就已經(jīng)夠weight，那weight=W1+W2+......+Wn=W1+W2+......+Wn-1.

  2.加上Wn后剛好夠weight,那自然地有weight=W1+W2+......+Wn.

  上面兩種情況一個有解，那問題就有解，于是我們可以把Wi從背包去掉倒退回去看weight的值。

  經(jīng)過一系列倒推，weight的值有下面三種情況：

  1. weight剛剛等于0 //說明有解

  2. weight<0 //不可能，所以無解

  3. weight>0 and 沒有W了 // 也不可能，無解

 def knap(weight,weights,n): //weight為包的容量，weights是一個所有重量的表，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

超級簡單吧！?。∪绻捎脛討B(tài)規(guī)劃解決，幾十行代碼要吧。這就12行代碼，簡單明了?。?！

感謝你能夠認真閱讀完這篇文章，希望小編分享的“python基于遞歸如何解決背包問題”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!