Python程式：查詢切割木棒並銷售相同長度木棒後的最大利潤

假設我們有一個名為 rodLen 的木棒長度列表。我們還有另外兩個整數，稱為 profit 和 cost，分別表示每單位長度的利潤和每次切割的成本。我們可以每單位長度獲得 profit 的利潤，但我們只能銷售長度都相同的木棒。我們還可以將一根木棒切割成兩部分，它們的長度為整數，但我們必須為每次切割支付 cost 的成本。我們可以根據需要切割木棒任意多次。我們需要找到可以獲得的最大利潤。

因此，如果輸入類似於 rodLen = [7, 10] profit = 6 cost = 4，則輸出將為 82，因為我們可以將長度為 7 的木棒切割成兩根木棒，長度分別為 5 和 2。然後，我們可以將長度為 10 的木棒切割成兩根木棒，長度均為 5。然後將所有 3 根長度為 5 的木棒出售，總利潤為 (5 + 5 + 5) * 6 - (2*4) = 82。

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

  • n := rodLen 的大小
  • 如果 n 等於 0，則
    • 返回 0
  • l_max := rodLen 的最大值
  • p_max := 0
  • 對於 cuts 從 1 到 l_max，執行以下操作：
    • p_cut := 0
    • 對於 rodLen 中的每個 rod_len，執行以下操作：
      • 如果 rod_len < cuts，則
        • 進入下一個迭代
      • c_count := rod_len / cuts
      • total_len := c_count * cuts
      • 如果 rod_len 等於 total_len，則
        • c_count := c_count - 1
      • curr_profit := total_len * profit - cost * c_count
      • 如果 curr_profit < 0，則
        • 進入下一個迭代
      • p_cut := p_cut + curr_profit
    • p_max := p_max 和 p_cut 的最大值
  • 返回 p_max

示例

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

def solve(rodLen, profit, cost):
   n = len(rodLen)
   if n == 0:
      return 0
   l_max = max(rodLen)
   p_max = 0

   for cuts in range(1, l_max + 1):
      p_cut = 0
      for rod_len in rodLen:
         if rod_len < cuts:
            continue
         c_count = rod_len // cuts
         total_len = c_count * cuts
         if rod_len == total_len:
            c_count -= 1
         curr_profit = total_len * profit - cost * c_count
         if curr_profit < 0:
            continue
         p_cut += curr_profit
      p_max = max(p_max, p_cut)
   return p_max

rodLen = [7, 10]
profit = 6
cost = 4
print(solve(rodLen, profit, cost))

輸入

[7, 10], 6, 4

輸出

82

更新於： 2021年10月18日

396 次檢視

開啟你的 職業生涯

完成課程獲得認證

開始學習
廣告