資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究0-1 揹包問題的 Python 程式
在本文中，我們將學習如何解決下面給出的問題陳述。
問題陳述 - 我們給出了 n 個專案的重量和價值，我們需要把這些專案放入一個容量為 W 的包中，最大容量為 w。我們需要攜帶最多數量的專案並返回其價值。
現在，讓我們觀察下面實現中的解決方案 -
# 蠻力法
示例
#Returns the maximum value that can be stored by the bag def knapSack(W, wt, val, n): # initial conditions if n == 0 or W == 0 : return 0 # If weight is higher than capacity then it is not included if (wt[n-1] > W): return knapSack(W, wt, val, n-1) # return either nth item being included or not else: return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # To test above function val = [50,100,150,200] wt = [8,16,32,40] W = 64 n = len(val) print (knapSack(W, wt, val, n))
輸出
350
#動態方法
示例
# a dynamic approach # Returns the maximum value that can be stored by the bag def knapSack(W, wt, val, n): K = [[0 for x in range(W + 1)] for x in range(n + 1)] #Table in bottom up manner for i in range(n + 1): for w in range(W + 1): if i == 0 or w == 0: K[i][w] = 0 elif wt[i-1] <= w: K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) else: K[i][w] = K[i-1][w] return K[n][W] #Main val = [50,100,150,200] wt = [8,16,32,40] W = 64 n = len(val) print(knapSack(W, wt, val, n))
輸出
350
所有變數都宣告在區域性作用域中，其引用關係在上圖中可以看到。
結論
在本文中，我們學習瞭如何為 0-1 揹包問題編寫 Python 程式。
更新於： 2019 年 12 月 20 日
5 千次+瀏覽
廣告