Python基于動態(tài)規(guī)劃算法解決01背包問題實例
更新時間：2017年12月06日 12:26:10 作者：littlethunder
這篇文章主要介紹了Python基于動態(tài)規(guī)劃算法解決01背包問題,結合實例形式分析了Python動態(tài)規(guī)劃算法解決01背包問題的原理與具體實現(xiàn)技巧,需要的朋友可以參考下
本文實例講述了Python基于動態(tài)規(guī)劃算法解決01背包問題。分享給大家供大家參考，具體如下：
在01背包問題中，在選擇是否要把一個物品加到背包中，必須把該物品加進去的子問題的解與不取該物品的子問題的解進行比較，這種方式形成的問題導致了許多重疊子問題，使用動態(tài)規(guī)劃來解決。n=5是物品的數(shù)量，c=10是書包能承受的重量，w=[2,2,6,5,4]是每個物品的重量，v=[6,3,5,4,6]是每個物品的價值，先把遞歸的定義寫出來：
然后自底向上實現(xiàn)，代碼如下：
def bag(n,c,w,v):
res=[[-1 for j in range(c+1)] for i in range(n+1)]
for j in range(c+1):
res[0][j]=0
for i in range(1,n+1):
for j in range(1,c+1):
res[i][j]=res[i-1][j]
if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:
res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
return res
def show(n,c,w,res):
print('最大價值為:',res[n][c])
x=[False for i in range(n)]
j=c
for i in range(1,n+1):
if res[i][j]>res[i-1][j]:
x[i-1]=True
j-=w[i-1]
print('選擇的物品為:')
for i in range(n):
if x[i]:
print('第',i,'個,',end='')
print('')
if __name__=='__main__':
n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,4,6]
res=bag(n,c,w,v)
show(n,c,w,res)
輸出結果如下：
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數(shù)使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》
希望本文所述對大家Python程序設計有所幫助。
相關文章
python NumPy ndarray二維數(shù)組 按照行列求平均實例
今天小編就為大家分享一篇python NumPy ndarray二維數(shù)組 按照行列求平均實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-11-11
這篇文章主要介紹了給Python中的MySQLdb模塊添加超時功能的教程,timeout功能在服務器的運維當中非常有用,需要的朋友可以參考下2015-05-05
這篇文章主要為大家詳細介紹了Python面向對象之Web靜態(tài)服務器，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-09-09
詳解python實現(xiàn)可視化的MD5、sha256哈希加密小工具
這篇文章主要介紹了詳解python實現(xiàn)可視化的MD5、sha256哈希加密小工具，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-09-09
這篇文章主要給大家介紹了關于為什么你還不懂得怎么使用Python協(xié)程的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用Python具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-05-05
這篇文章主要介紹了python批量啟動多線程代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-02-02
解決Python報錯:SyntaxError:?invalid?character?‘，‘?(U+FF0C)
Python中的 SyntaxError錯誤是Python語言中常見的異常錯誤類型之一,表示語法錯誤,下面這篇文章主要給大家介紹了關于解決Python報錯:SyntaxError:?invalid?character?‘，‘?(U+FF0C)的相關資料,需要的朋友可以參考下2022-12-12
今天小編就為大家分享一篇python科學計算之scipy——optimize用法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-11-11
基于PyQt5實現(xiàn)狀態(tài)欄(statusBar)顯示和隱藏功能
這篇文章主要為大家詳細介紹了如何利用PyQt5實現(xiàn)狀態(tài)欄顯示和隱藏功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-08-08
pathlib是跨平臺的、面向對象的路徑操作模塊,可適用于不同的操作系統(tǒng),其操作對象是各種操作系統(tǒng)中使用的路徑,下面這篇文章主要給大家介紹了關于Python文件路徑處理模塊pathlib的相關資料,需要的朋友可以參考下2023-04-04