Python程式：以最佳化方式填充水果並找到最小成本

假設我們有一個名為 fruits 的列表以及另外兩個值 k 和 cap。其中每個 fruits[i] 都有三個值：[c, s, t]，這表示水果 i 的每個水果成本為 c，每個水果的大小為 s，並且共有 t 個。k 表示容量為 cap 的水果籃的數量。我們希望在以下約束條件下填充水果籃，並按照以下順序進行：-

  • 每個籃子只能裝同一型別的水果
  • 每個籃子應該儘可能裝滿
  • 每個籃子應該儘可能便宜

因此，我們必須找到填充儘可能多的籃子所需的最低成本。

因此，如果輸入類似於 fruits = [[5, 2, 3],[6, 3, 2],[2, 3, 2]] k = 2 cap = 4，則輸出將為 12，因為我們可以取兩個水果 0，因為用這兩個水果，我們可以使第一個籃子裝滿，總大小為 2+2=4，成本為 5+5=10。然後，我們使用一個水果 2，因為它更便宜。這花費了 2 個單位。

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

  • options := 一個新列表
  • 對於 fruits 中的每個三元組 (c, s, t)，執行以下操作：
    • 當 t > 0 時，執行以下操作：
      • fnum := (cap / s) 的向下取整和 t 的最小值
      • 如果 fnum 等於 0，則
        • 退出迴圈
      • bnum := t / fnum 的向下取整
      • 在 options 的末尾插入三元組 (cap - fnum * s, fnum * c, bnum)
      • t := t - bnum * fnum
  • ans := 0
  • 對於排序後的 options 列表中的每個三元組 (left_cap, bcost, bnum)，執行以下操作：
    • bfill := k 和 bnum 的最小值
    • ans := ans + bcost * bfill
    • k := k - bfill
    • 如果 k 等於 0，則
      • 退出迴圈
  • 返回 ans

示例

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

def solve(fruits, k, cap):
   options = []
   for c, s, t in fruits:
      while t > 0:
         fnum = min(cap // s, t)
         if fnum == 0:
            break
         bnum = t // fnum

         options.append((cap - fnum * s, fnum * c, bnum))
         t -= bnum * fnum
   ans = 0
   for left_cap, bcost, bnum in sorted(options):
      bfill = min(k, bnum)
      ans += bcost * bfill
      k -= bfill
      if k == 0:
         break

   return ans

fruits = [[5, 2, 3],[6, 3, 2],[2, 3, 2]]
k = 2
cap = 4
print(solve(fruits, k, cap))

輸入

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

輸出

12

更新於： 2021年10月18日

1K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.