Python程式：查詢卡車上可放置的最大單位數

假設我們有一組箱子，用一個二維陣列 boxTypes 表示，其中 boxTypes[i] 包含兩個元素 [第 i 種箱子的數量，第 i 種箱子每個箱子的單位數]。現在我們還有一個值 k，它是卡車上可以放置的最大箱子數量。我們可以選擇任何箱子放在卡車上，只要箱子的數量不超過 k。我們需要找到可以放在卡車上的最大總單位數。

因此，如果輸入類似於 boxTypes = [[2,4],[3,3],[4,2]], k = 6，則輸出將為 19，因為有

  • 2 個型別 1 的箱子，每個箱子包含 4 個單位

  • 3 個型別 2 的箱子，每個箱子包含 3 個單位

  • 4 個型別 3 的箱子，每個箱子包含 2 個單位

由於 k = 6，我們可以取所有型別 1 和 2 的箱子，以及型別 3 的一個箱子，所以將會有 (2*4) + (3*3) + 2 = 8 + 9 +2 = 19 個物品。

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

  • 根據每個箱子中存在的物品數量對 boxTypes 進行排序

  • total := 0, fill := 0

  • 對於 boxTypes 中的每個 i，執行以下操作：

    • 如果 fill + i[0] <= k，則

      • fill := fill + i[0]

      • total := total + i[0] * i[1]

    • 否則，

      • total := total + (k - fill) * i[1]

      • 退出迴圈

  • 返回 total

示例（Python）

讓我們看看以下實現以獲得更好的理解：

 線上演示

def solve(boxTypes, k):
   boxTypes.sort(key = lambda x : x[1], reverse = True)
   total = 0
   fill = 0
   for i in boxTypes:
      if fill + i[0] <= k:
         fill += i[0]
         total += i[0] * i[1]
      else:
         total += (k - fill) * i[1]
         break
   return total

boxTypes = [[2,4],[3,3],[4,2]]
k = 6
print(solve(boxTypes, k))

輸入

[[2,4],[3,3],[4,2]], 6

輸出

19

更新於： 2021年5月18日

626 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告