Python基于回溯法解決01背包問題實例
更新時間：2017年12月06日 12:34:05 作者：littlethunder
這篇文章主要介紹了Python基于回溯法解決01背包問題,結(jié)合實例形式分析了Python回溯法采用深度優(yōu)先策略搜索解決01背包問題的相關(guān)操作技巧,需要的朋友可以參考下
本文實例講述了Python基于回溯法解決01背包問題。分享給大家供大家參考，具體如下：
同樣的01背包問題，前面采用動態(tài)規(guī)劃的方法，現(xiàn)在用回溯法解決?；厮莘ú捎蒙疃葍?yōu)先策略搜索問題的解，不多說，代碼如下：
bestV=0
curW=0
curV=0
bestx=None
def backtrack(i):
global bestV,curW,curV,x,bestx
if i>=n:
if bestV<curV:
bestV=curV
bestx=x[:]
else:
if curW+w[i]<=c:
x[i]=True
curW+=w[i]
curV+=v[i]
backtrack(i+1)
curW-=w[i]
curV-=v[i]
x[i]=False
backtrack(i+1)
if __name__=='__main__':
n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,4,6]
x=[False for i in range(n)]
backtrack(0)
print(bestV)
print(bestx)
運行結(jié)果如下：
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
這篇文章主要介紹了Python文件的壓縮與解壓，Python進行文件、文件夾壓縮與解壓，用到的是zipfile的第三方依賴庫。根據(jù)不同應(yīng)用場景封裝了幾個方法，下文相關(guān)內(nèi)容需要的小伙伴可以參考一下2022-04-04
這篇文章主要介紹了Tensorflow全局設(shè)置可見GPU編號操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06
特點是多平臺，一個腳本內(nèi)可以備份多個數(shù)據(jù)庫，并分別打包上傳到ftp進行備份。調(diào)用了mysqldump及tar來進行數(shù)據(jù)庫dump及打包。 具體參數(shù)說明參見源文件2008-08-08
這篇文章主要介紹了keras輸出預(yù)測值和真實值方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06
這篇文章主要為大家詳細介紹了python遞歸實現(xiàn)鏈表快速倒轉(zhuǎn)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
redis是一個key-value存儲系統(tǒng)，value的類型包括string(字符串)，list(鏈表)，set(集合)，zset(有序集合)，hash(哈希類型)。這篇文章主要介紹了Python操作redis和mongoDB的方法,需要的朋友可以參考下2019-12-12
這篇文章主要為大家詳細介紹了Python從零開始創(chuàng)建區(qū)塊鏈的步驟 ，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-03-03
這篇文章主要介紹了Python 實現(xiàn)過濾掉列表中唯一值，文章內(nèi)容主要利用Python代碼實現(xiàn)過濾掉列表中的唯一值的功能,需要的朋友可以參考一下2021-11-11
Python函數(shù)式編程指南（二）：從函數(shù)開始
這篇文章主要介紹了Python函數(shù)式編程指南（二）：從函數(shù)開始,本文講解了定義一個函數(shù)、使用函數(shù)賦值、閉包、作為參數(shù)等內(nèi)容,需要的朋友可以參考下2015-06-06
Python實現(xiàn)繪制3D地球旋轉(zhuǎn)效果
這篇文章主要為大家詳細介紹了如何利用Python實現(xiàn)繪制出3D地球旋轉(zhuǎn)的效果，文中的示例代碼講解詳細，具有一定的借鑒價值，需要的可以參考一下2023-02-02