本文實例講述了Python基于動態規劃算法解決01背包問題。分享給大家供大家參考，具體如下：
在01背包問題中，在選擇是否要把一個物品加到背包中，必須把該物品加進去的子問題的解與不取該物品的子問題的解進行比較，這種方式形成的問題導致了許多重疊子問題，使用動態規劃來解決。n=5是物品的數量，c=10是書包能承受的重量，w=[2,2,6,5,4]是每個物品的重量，v=[6,3,5,4,6]是每個物品的價值，先把遞歸的定義寫出來：
然后自底向上實現，代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
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 resdef 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程序設計有所幫助。
原文鏈接：http://blog.csdn.net/littlethunder/article/details/26575417
