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