Chi phí tối thiểu để cắt tấm bảng thành các ô vuông trong Python

Cho một tấm bảng dài p và rộng q. Ta cần cắt bảng thành p * q ô vuông sao cho chi phí cắt là nhỏ nhất. Chi phí cắt cho mỗi cạnh sẽ được cho trước.

Ví dụ, với X_slice = [3, 2, 4, 2, 5], Y_slice = [5, 2, 3]:

Kết quả sẽ là 65.

Thuật toán giải quyết

• res := 0.
• horizontal := 1, vertical := 1.
• i := 0, j := 0.
• Sắp xếp X_slice và Y_slice giảm dần.
• Trong khi i < m và j < n:
  • Nếu X_slice[i] > Y_slice[j]:
    • res += X_slice[i] * vertical.
    • horizontal += 1, i += 1.
  • Ngược lại:
    • res += Y_slice[j] * horizontal.
    • vertical += 1, j += 1.
• Xử lý các phần tử còn lại của X_slice và Y_slice tương tự.
• Trả về res.

Ví dụ minh họa

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

Đầu vào

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

Đầu ra

65