欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python基于遞歸解決背包問題詳解

 更新時間:2019年07月03日 10:52:04   作者:thelostmathematician  
這篇文章主要介紹了python基于遞歸解決背包問題,遞歸是個好東西,任何具有遞歸性質(zhì)的問題通過函數(shù)遞歸調(diào)用會變得很簡單。一個很復(fù)雜的問題,幾行代碼就能搞定,需要的朋友可以參考下

遞歸是個好東西,任何具有遞歸性質(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

超級簡單吧?。?!如果采用動態(tài)規(guī)劃解決,幾十行代碼要吧。這就12行代碼,簡單明了!?。?br />

以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • 用python wxpy管理微信公眾號并利用微信獲取自己的開源數(shù)據(jù)

    用python wxpy管理微信公眾號并利用微信獲取自己的開源數(shù)據(jù)

    這篇文章主要介紹了用python wxpy管理微信公眾號并利用微信獲取自己的開源數(shù)據(jù),本文通過實例代碼給大家介紹的非常詳細,具有一定的參考借鑒價值,需要的朋友可以參考下
    2019-07-07
  • 巧用python和libnmapd,提取Nmap掃描結(jié)果

    巧用python和libnmapd,提取Nmap掃描結(jié)果

    本文將會講述一系列如何使用一行代碼解析 nmap 掃描結(jié)果,其中會在 Python 環(huán)境中使用到 libnmap 里的 NmapParser 庫,這個庫可以很容易的幫助我們解析 nmap 的掃描結(jié)果
    2016-08-08
  • Python隊列、進程間通信、線程案例

    Python隊列、進程間通信、線程案例

    這篇文章主要介紹了Python隊列、進程間通信、線程,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-10-10
  • PyCharm連接遠程服務(wù)器配置的全過程

    PyCharm連接遠程服務(wù)器配置的全過程

    這篇文章主要介紹了PyCharm連接遠程服務(wù)器配置的全過程,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-06-06
  • 實例解析Python設(shè)計模式編程之橋接模式的運用

    實例解析Python設(shè)計模式編程之橋接模式的運用

    這篇文章主要介紹了Python設(shè)計模式編程之橋接模式的運用,橋接模式主張把抽象部分與它的實現(xiàn)部分分離,需要的朋友可以參考下
    2016-03-03
  • OpenCV半小時掌握基本操作之邊緣檢測

    OpenCV半小時掌握基本操作之邊緣檢測

    這篇文章主要介紹了OpenCV基本操作之邊緣檢測,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-09-09
  • Python操作Mongodb數(shù)據(jù)庫的方法小結(jié)

    Python操作Mongodb數(shù)據(jù)庫的方法小結(jié)

    這篇文章主要介紹了Python操作Mongodb數(shù)據(jù)庫的方法,結(jié)合實例形式總結(jié)分析了Python針對MongoDB數(shù)據(jù)庫的基本模塊導入、連接、增刪改查及排序等相關(guān)操作技巧,需要的朋友可以參考下
    2019-09-09
  • Python通過遞歸遍歷出集合中所有元素的方法

    Python通過遞歸遍歷出集合中所有元素的方法

    這篇文章主要介紹了Python通過遞歸遍歷出集合中所有元素的方法,實例分析了Python遍歷集合元素的技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-02-02
  • 使用LibTorch進行C++調(diào)用pytorch模型方式

    使用LibTorch進行C++調(diào)用pytorch模型方式

    這篇文章主要介紹了使用LibTorch進行C++調(diào)用pytorch模型方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-12-12
  • 詳解Python中的多線程

    詳解Python中的多線程

    這篇文章主要介紹了Python中的多線程,線程就是進程中一條執(zhí)行程序的執(zhí)行路徑,一個程序至少有一條執(zhí)行路徑,本文給大家介紹的非常詳細,需要的朋友可以參考下
    2022-06-06

最新評論