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

Khái niệm

Cho tấm bảng kích thước p×q, cần cắt thành p×q ô vuông. Chi phí cắt mỗi cạnh cho trước. Tìm thứ tự cắt để tổng chi phí nhỏ nhất.

Ví dụ minh họa: Tổng chi phí tối thiểu = 65 với các bước cắt lần lượt các cạnh chi phí cao trước.

Phương pháp Tham lam (Greedy)

Tổng chi phí S = Σ bᵢ×xᵢ, trong đó xᵢ là chi phí cắt, bᵢ là số mảnh tại thời điểm cắt. Tổng bᵢ không đổi. Để tối thiểu S, cắt các cạnh chi phí cao nhất sớm nhất (khi bᵢ còn nhỏ).

Thuật toán:

1. Sắp xếp chi phí cắt ngang (X) và dọc (Y) giảm dần.
2. Duyệt hai mảng, luôn chọn chi phí lớn hơn để cắt, cập nhật số mảnh ngang/dọc.
3. Cộng dồn chi phí còn lại.

Ví dụ (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, 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[5]={3,2,4,2,5};
    int Y1[3]={5,2,3};
    cout<<minimumCostOfBreaking(X1,Y1,5,3);
    return 0;
}

Đầu ra

65