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