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

แนวคิด

กระดานขนาด p×q ต้องตัดเป็น p×q ชิ้นสี่เหลี่ยมจัตุรัส ต้นทุนตัดแต่ละขอบกำหนดไว้ หาลำดับการตัดที่ให้ต้นทุนรวมน้อยที่สุด

ตัวอย่าง: ต้นทุนรวมต่ำสุด = 65 โดยลำดับ: - ตัดแนวนอน cost 5: 0 + 5×1 = 5 - ตัดแนวตั้ง cost 5: 5 + 5×2 = 15 - ตัดแนวตั้ง cost 4: 15 + 4×2 = 23 - ตัดแนวนอน cost 3: 23 + 3×3 = 32 - ตัดแนวตั้ง cost 3: 32 + 3×3 = 41 - ตัดแนวนอน cost 2: 41 + 2×4 = 49 - ตัดแนวตั้ง cost 2: 49 + 2×4 = 57 - ตัดแนวตั้ง cost 2: 57 + 2×4 = 65

วิธีการแก้ปัญหา (Greedy)

Total Cost S = Σ bi×xi โดย bi = จำนวนชิ้นที่มีอยู่เมื่อตัดขอบ xi

ผลรวม bi คงที่ → ต้องตัดขอบที่มี cost สูงสุดก่อน (ทำให้ bi น้อยที่สุด) → เรียง cost แบบ descending แล้วเลือกทีละขอบ

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

#include <bits/stdc++.h>
using namespace std;

int minimumCostOfBreaking(int X1[], int Y1[], int p, int q){
    int res1 = 0;
    sort(X1, X1 + p, greater<int>());
    sort(Y1, Y1 + q, greater<int>());
    int hzntl = 1, vert = 1;
    int i = 0, j = 0;
    while (i < p && j < q){
        if (X1[i] > Y1[j]){
            res1 += X1[i] * vert;
            hzntl++; i++;
        } else {
            res1 += Y1[j] * hzntl;
            vert++; j++;
        }
    }
    int total = 0;
    while (i < p) total += X1[i++];
    res1 += total * vert;
    total = 0;
    while (j < q) total += Y1[j++];
    res1 += total * hzntl;
    return res1;
}

int main(){
    int p = 6, q = 4;
    int X1[p-1] = {3, 2, 4, 2, 5};
    int Y1[q-1] = {5, 2, 3};
    cout << minimumCostOfBreaking(X1, Y1, p-1, q-1);
    return 0;
}

ผลลัพธ์

65