Python 中將木板切割成正方形的最小成本

假設我們有一個長為 p、寬為 q 的木板；我們需要將該木板切割成 p*q 個正方形，使得切割成本儘可能低。每條邊的切割成本將給出。

因此，如果輸入類似於 X_slice = [3,2,4,2,5]，Y_slice = [5,2,3]

則輸出將為 65

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

  • res := 0
  • horizontal := 1, vertical := 1
  • i := 0, j := 0
  • 當 i < m 且 j < n 時，執行以下操作
    • 如果 X_slice[i] > Y_slice[j]，則
      • res := res + X_slice[i] * vertical
      • horizontal := horizontal + 1
      • i := i + 1
    • 否則，
      • res := res + Y_slice[j] * horizontal
      • vertical := vertical + 1
      • j := j + 1
  • total := 0
  • 當 i < m 時，執行以下操作
    • total := total + X_slice[i]
    • i := i + 1
  • res := res + total * vertical
  • total := 0
  • 當 j < n 時，執行以下操作
    • total := total + Y_slice[j]
    • j := j + 1
  • res := res + total * horizontal
  • 返回 res

示例

讓我們看看以下實現以更好地理解：

 線上演示

def minCost(X_slice, Y_slice, m, n):
   res = 0
   X_slice.sort(reverse = True)
   Y_slice.sort(reverse = True)
   horizontal = 1
   vertical = 1
   i = 0
   j = 0
   while i < m and j < n:
      if (X_slice[i] > Y_slice[j]):
         res += X_slice[i] * vertical
         horizontal += 1
         i += 1
      else:
         res += Y_slice[j] * horizontal
         vertical += 1
         j += 1
   total = 0
   while (i < m):
      total += X_slice[i]
      i += 1
   res += total * vertical
   total = 0
   while (j < n):
      total += Y_slice[j]
      j += 1
   res += total * horizontal
   return res
m = 6; n = 4
X_slice = [3,2,4,2,5]
Y_slice = [5,2,3]
print(minCost(X_slice, Y_slice, m-1, n-1))

輸入

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

輸出

65

更新於: 2020年8月27日

143 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告