หาต้นทุนน้อยที่สุดในการตัดกระดานเป็นสี่เหลี่ยมจัตุรัสใน Python

Minimum Cost to Cut Board into Squares

กระดานขนาด p x q ต้องตัดเป็น p*q สี่เหลี่ยมจัตุรัสขนาด 1x1 ต้นทุนการตัดแต่ละขอบกำหนดให้ (Horizontal cuts และ Vertical cuts) ต้องการหาลำดับการตัดที่ให้ต้นทุนรวมน้อยที่สุด

ตัวอย่าง: X_slice = [3,2,4,2,5] (ต้นทุนตัดแนวนอน), Y_slice = [5,2,3] (ต้นทุนตัดแนวตั้ง) → ต้นทุนต่ำสุด = 65

กลยุทธ์ Greedy

1. เรียงต้นทุนตัดทั้งสองแนวจากมากไปน้อย
2. เลือกตัดขอบที่มีต้นทุนสูงสุดก่อน (เพราะจะคูณกับจำนวนชิ้นที่น้อยกว่า)
3. เก็บจำนวนชิ้นแนวนอน (horizontal) และแนวตั้ง (vertical) ปัจจุบัน
4. เมื่อตัดแนวนอน: ต้นทุน += X_slice[i] * vertical, horizontal++
5. เมื่อตัดแนวตั้ง: ต้นทุน += Y_slice[j] * horizontal, vertical++
6. ตัดขอบที่เหลือทีละขอบ

โค้ดตัวอย่าง Python

def minCost(X_slice, Y_slice, m, n):
    X_slice.sort(reverse=True)
    Y_slice.sort(reverse=True)
    horizontal = vertical = 1
    i = j = 0
    res = 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
    while i < m:
        res += X_slice[i] * vertical
        i += 1
    while j < n:
        res += Y_slice[j] * horizontal
        j += 1
    return res

X = [3,2,4,2,5]
Y = [5,2,3]
print(minCost(X, Y, len(X), len(Y)))  # 65