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入門(mén)與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
這篇文章主要介紹了Jupyter notebook如何修改平臺(tái)字體,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-05-05
這篇文章主要介紹了python 如何讀取列表中字典的value值，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-02-02
這篇文章主要為大家詳細(xì)介紹了Windows下python2.7.8安裝圖文教程，在安裝過(guò)程中出現(xiàn)“python不是內(nèi)部或外部命令”提示的解決方法，感興趣的小伙伴們可以參考一下2016-05-05
如何使用VSCode愉快的寫(xiě)Python于調(diào)試配置步驟
從我的使用經(jīng)驗(yàn)出發(fā)，可以說(shuō)VSCode用來(lái)寫(xiě)Python真的是再合適不過(guò)了，你將體驗(yàn)到絲滑的編程體驗(yàn)和無(wú)限擴(kuò)展的可能。而且，如果你的項(xiàng)目是包含多種語(yǔ)言的，比如Web開(kāi)發(fā)，你不必再開(kāi)多個(gè)編輯器和其他工具，因?yàn)檫@一切都可以在VSCode里完成了2018-04-04
Python比較文件夾比另一同名文件夾多出的文件并復(fù)制出來(lái)的方法
這篇文章主要介紹了Python比較文件夾比另一同名文件夾多出的文件并復(fù)制出來(lái)的方法,涉及Python針對(duì)文件與文件夾的操作技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-03-03
這篇文章主要介紹了Python 連接 MySQL 的幾種方法，幫助大家更好的理解和使用python，感興趣的朋友可以了解下2020-09-09
從零學(xué)python系列之新版本導(dǎo)入httplib模塊報(bào)ImportError解決方案
在使用新版python打開(kāi)舊版本代碼的時(shí)候，可能會(huì)有些報(bào)錯(cuò)或者不兼容的情況出現(xiàn)，今天我們就來(lái)分析其中的一種情況2014-05-05
這篇文章主要為大家詳細(xì)介紹了如何利用Python實(shí)現(xiàn)文件夾整理下載,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,有需要的小伙伴可以參考一下2023-09-09
pandas.DataFrame.rank方法支持不同的排序方式,如按行或列、升序或降序等,主要參數(shù)包括axis控制按行或列排名,method定義相同值的處理方式,numeric_only指定是否僅對(duì)數(shù)字列排序,na_option設(shè)置NaN值的排序方法,ascending確定排序方向,pct決定是否以百分比形式展示排名2024-09-09
Python數(shù)據(jù)處理篇之Sympy系列(五)---解方程
這篇文章主要介紹了Python數(shù)據(jù)處理篇之Sympy系列(五)---解方程,非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-10-10