溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了python基于遞歸如何解決背包問題，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
遞歸是個好東西，任何具有遞歸性質的問題通過函數遞歸調用會變得很簡單。一個很復雜的問題，幾行代碼就能搞定。
最簡單的遞歸問題：現有重量為weight的包，有若干重量分別為W1,W2.....Wn的物品，試問能否從物品中選出若干件而且重量剛好為weight?
weight具體是怎么構成的，有下面兩種情況（假設挑選到Wn時，剛好夠weight)：
1. 從Wn-1開始就已經夠weight，那weight=W1+W2+......+Wn=W1+W2+......+Wn-1.
2.加上Wn后剛好夠weight,那自然地有weight=W1+W2+......+Wn.
上面兩種情況一個有解，那問題就有解，于是我們可以把Wi從背包去掉倒退回去看weight的值。
經過一系列倒推，weight的值有下面三種情況：
1. weight剛剛等于0 //說明有解
2. weight<0 //不可能，所以無解
3. weight>0 and 沒有W了 // 也不可能，無解
def knap(weight,weights,n): //weight為包的容量，weights是一個所有重量的表，n為重量數量 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
超級簡單吧！！！如果采用動態規劃解決，幾十行代碼要吧。這就12行代碼，簡單明了！！！
感謝你能夠認真閱讀完這篇文章，希望小編分享的“python基于遞歸如何解決背包問題”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
