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