C++でボードを正方形にカットするための最小コスト

コンセプト

長さ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

メソッド

このタイプの問題は、欲張りアプローチを実装することで解決できます。総コストが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