Python實現揹包問題：求解可多次選取物品的最大價值

假設我們有兩個長度相同的列表，分別稱為weights（重量）和values（價值），還有一個capacity（容量）值。其中weights[i]和values[i]分別表示第i個物品的重量和價值。如果我們最多可以承受capacity重量，並且可以對每個物品選取任意數量的副本，我們需要找到可以獲得的最大價值。

例如，如果輸入為weights = [1, 2, 3]，values = [1, 5, 3]，capacity = 5，則輸出為11。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式dp()。它將接收i和k作為引數。
  • 如果i等於weights的長度，則
    • 返回0
  • ans := dp(i + 1, k)
  • 如果k >= weights[i]，則
    • ans := ans和dp(i, k - weights[i]) + values[i]中的最大值
  • 返回ans
  • 在主方法中執行以下操作：
  • 返回dp(0, capacity)

讓我們看下面的實現來更好地理解：

示例

線上演示

class Solution:
   def solve(self, weights, values, capacity):
      def dp(i, k):
         if i == len(weights):
            return 0
         ans = dp(i + 1, k)
         if k >= weights[i]:
            ans = max(ans, dp(i, k - weights[i]) + values[i])
         return ans
      return dp(0, capacity)
ob = Solution()
weights = [1, 2, 3]
values = [1, 5, 3]
capacity = 5
print(ob.solve(weights, values, capacity))

輸入

[1, 2, 3], [1,5,3], 5

輸出

11

更新於：2020年10月20日

507 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告