컨셉
길이가 p이고 너비가 q인 보드가 있다고 가정하면 이 보드를 p*q 정사각형으로 분할하여 절단 비용이 최소가 되도록 해야 합니다. 이 보드의 경우 각 모서리에 대한 절단 비용이 제공됩니다. 간단히 말해서 비용을 최소화할 수 있는 절단 순서를 선택해야 합니다.
예시
위의 보드와 관련하여 정사각형으로 자르는 최적의 방법은 -
위의 경우 총 최소 비용은 65입니다. 다음 단계를 수행하여 계산됩니다.
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
방법
이러한 유형의 문제는 greedy approach를 구현하여 해결할 수 있습니다. 총 비용이 S로 처리되면 S =b1x1 + b2x2 … + bkxk가 됩니다. 여기서 xi는 특정 모서리 절단 비용으로 처리되고 bi는 해당 계수입니다. 계수 bi는 모서리를 구현하기 위해 경쟁한 총 절단 수에 의해 결정됩니다. xi 절단 과정의 끝에서.
계수의 합은 항상 일정하므로 S가 최소가 되도록 얻을 수 있는 bi의 분포를 계산하려고 합니다. 그렇게 하기 위해 우리는 최대한 빨리 가장 큰 비용 가장자리에서 절단을 수행하여 최적의 S에 도달합니다. 동일한 비용을 갖는 가장자리가 여러 개 발견되면 먼저 그 중 하나를 제거하거나 절단할 수 있습니다.
C++ 프로그램
다음은 위의 접근 방식을 구현하는 솔루션입니다. 먼저 에지 커팅 비용을 역순으로 정렬한 다음 솔루션을 구축하는 데 더 높은 비용에서 더 낮은 비용으로 반복합니다. 모서리를 선택할 때마다 상대방 수는 1씩 증가하며 매번 해당 모서리 절단 비용이 곱해집니다.
예시
// 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;
} 출력
65