Python程式：求解揹包中物品所能獲得的最大價格

假設我們有兩個數字列表。一個稱為weights（重量），另一個稱為values（價值）。它們的長度相同。我們還有兩個值，capacity（容量）和count（數量）。其中weights[i]和values[i]分別表示第i個物品的重量和價值。我們最多可以容納capacity重量的物品，並且最多可以攜帶count件物品。每個物品只能取一件，我們需要找到可以獲得的最大價值。

例如，如果輸入為weights = [2, 2, 4, 6]，values = [15, 15, 20, 35]，capacity = 8，count = 3，則輸出為50，因為我們可以選擇前3個物品，總重量為8。

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

  • items := 透過組合weights和values建立一個包含重量和價值對的列表

  • 定義一個函式dp()。它將接收i, cp, ct作為引數

  • 如果i等於items的長度或ct等於0，則

    • 返回0.0

  • (w, v) := items[i]

  • ans := dp(i + 1, cp, ct)

  • 如果cp >= w，則

    • ans := ans和dp(i + 1, cp - w, ct - 1) + v中的最大值

  • 返回ans

  • 在主方法中返回dp(0, capacity, count)

示例

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

 線上演示

class Solution:
   def solve(self, weights, values, capacity, count):
      items = list(zip(weights, values))
      def dp(i, cp, ct):
         if i == len(items) or ct == 0:
            return 0.0
         w, v = items[i]
         ans = dp(i + 1, cp, ct)
         if cp >= w:
            ans = max(ans, dp(i + 1, cp - w, ct - 1) + v)
         return ans
      return int(dp(0, capacity, count))
ob = Solution()
weights = [2, 2, 4, 6]
values = [15, 15, 20, 35]
capacity = 8
count = 3
print(ob.solve(weights, values, capacity, count))

輸入

[2, 2, 4, 6], [15, 15, 20, 35], 8, 3

輸出

50

更新於：2020-12-22

310 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告