Chi phí tối thiểu để cắt bảng thành hình vuông trong C ++

Khái niệm

Giả sử một tấm ván có chiều dài p và chiều rộng q được đưa ra, chúng ta yêu cầu bẻ tấm ván này thành các hình vuông p * q sao cho chi phí phá vỡ là ít nhất. Đối với bảng này, chi phí cắt cho mỗi cạnh sẽ được đưa ra. Tóm lại, chúng tôi yêu cầu lựa chọn trình tự cắt giảm như vậy để giảm thiểu chi phí.

Ví dụ

Đối với bảng trên, cách tối ưu để cắt thành hình vuông là -

Tổng chi phí tối thiểu trong trường hợp trên là 65. Nó được tính toán đánh giá thực hiện các bước sau.

Initial Value : Total_cost = 0
Total_cost = Total_cost + edge_cost * total_pieces
Cost 5 Horizontal cut Cost = 0 + 5*1 = 5
Cost 5 Vertical cut Cost = 5 + 5*2 = 15
Cost 4 Vertical cut Cost = 15 + 4*2 = 23
Cost 3 Horizontal cut Cost = 23 + 3*3 = 32
Cost 3 Vertical cut Cost = 32 + 3*3 = 41
Cost 2 Horizontal cut Cost = 41 + 2*4 = 49
Cost 2 Vertical cut Cost = 49 + 2*4 = 57
Cost 2 Vertical cut Cost = 57 + 2*4 = 65

Phương pháp

Loại vấn đề này có thể được giải quyết bằng cách tiếp cận tham lam. Nếu tổng chi phí được coi là S, thì S =b1x1 + b2x2… + bkxk, trong đó xi được coi là chi phí của việc cắt cạnh nhất định và bi là hệ số tương ứng, Hệ số bi được xác định bằng tổng số lần cắt mà chúng ta đã cạnh tranh thực hiện cạnh xi ở cuối quá trình cắt.

Chúng ta nên nhận thấy rằng tổng các hệ số luôn không đổi, do đó chúng ta muốn tính toán một phân phối của bi có thể thu được sao cho S là nhỏ nhất. Để làm như vậy, chúng tôi thực hiện việc cắt giảm cạnh chi phí lớn nhất càng sớm càng tốt, điều này sẽ đạt đến mức S. Tối ưu. Nếu chúng tôi gặp một số cạnh có chi phí bằng nhau, chúng tôi có thể loại bỏ hoặc cắt bỏ bất kỳ cạnh nào trong số chúng.

Chương trình C ++

Sau đây là giải pháp thực hiện phương pháp trên, đầu tiên chúng tôi sắp xếp các chi phí cắt giảm theo thứ tự ngược lại, sau đó chúng tôi lặp lại chúng từ chi phí cao hơn đến chi phí thấp hơn để xây dựng giải pháp của chúng tôi. Mỗi lần chúng tôi chọn một cạnh, số lượng đối ứng được tăng lên 1, số này sẽ được nhân lên mỗi lần với chi phí cắt cạnh tương ứng.

Ví dụ

// C++ program to divide a board into p*q squares
#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;
}

Đầu ra

65