Chi phí tối thiểu để cắt một bảng thành các hình vuông bằng Python

Giả sử chúng ta có một bảng chiều dài p và chiều rộng q; chúng ta phải chia bảng này thành p * q số ô vuông sao cho chi phí phá vỡ là tối thiểu nhất có thể. Chi phí cắt giảm cho mỗi cạnh sẽ được đưa ra.

Vì vậy, nếu đầu vào giống như X_slice =[3,2,4,2,5], Y_slice =[5,2,3]

thì đầu ra sẽ là 65

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• res:=0
• ngang:=1, dọc:=1
• i:=0, j:=0
• while i
• nếu X_slice [i]> Y_slice [j], thì
  • res:=res + X_slice [i] * vertical
  • ngang:=ngang + 1
  • i:=i + 1
• nếu không,
  • res:=res + Y_slice [j] * ngang
  • vertical:=vertical + 1
  • j:=j + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

65