用 Python 将木板切成方块的最小成本

pythonserver side programmingprogramming更新于 2025/10/16 4:28:17

假设我们有一块长度为 p、宽度为 q 的木板；我们必须将这块木板分成 p*q 个方块，以使分解成本尽可能低。将给出每条边的切割成本。

因此，如果输入为 X_slice = [3,2,4,2,5], Y_slice = [5,2,3]

则输出为 65

要解决这个问题，我们将遵循以下步骤 −

res := 0
水平 := 1, 垂直 := 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))