logo

TechCodeview

基板を正方形に切断するための最小コスト

GfG Practice で試してみる 基板を正方形に切断するための最小コスト' title=

次元のボードが与えられた場合 n×m それをn×mの正方形に切る必要があります。水平または垂直エッジに沿ってカットを行うコストは、次の 2 つの配列で提供されます。

  • ×[] : 垂直方向のエッジ (長さ方向) に沿ってコストを削減します。
  • そして[] ：横方向（幅方向）のコストを削減します。

基板を最適に正方形に切断するために必要な最小の総コストを求めます。

例: 



入力： x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
出力： 42
説明：

最初はいいえ。水平セグメントの数 = 1 & いいえ垂直セグメントの数 = 1。
正方形にカットする最適な方法は次のとおりです。
4 (x から) を選択 -> 垂直カット コスト = 4 × 水平セグメント = 4
 これで、水平セグメント = 1、垂直セグメント = 2 になります。
4 (y から) を選択 -> 水平カット コスト = 4 × 垂直セグメント = 8
 これで、水平セグメント = 2 垂直セグメント = 2 になります。
3 (x から) を選択 -> 垂直カット コスト = 3 × 水平セグメント = 6
 これで、水平セグメント = 2 垂直セグメント = 3 になります。
2 (x から) を選択 -> 垂直カット コスト = 2 × 水平セグメント = 4
 これで、水平セグメント = 2 垂直セグメント = 4 になります。
2 (y から) を選択 -> 水平カット コスト = 2 × 垂直セグメント = 8
 これで、水平セグメント = 3 垂直セグメント = 4 になります。
1 (x から) を選択 -> 垂直カット コスト = 1 × 水平セグメント = 3
これで、水平セグメント = 3 垂直セグメント = 5 になります。
1 (x から) を選択 -> 垂直カット コスト = 1 × 水平セグメント = 3
これで、水平セグメント = 3 垂直セグメント = 6 になります。
1 (y から) を選択 -> 水平カット コスト = 1 × 垂直セグメント = 6
これで、水平セグメント = 4 垂直セグメント = 6 になります。
したがって、合計コスト = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42 となります。

入力： x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
出力： 15
説明：
最初はいいえ。水平セグメントの数 = 1 & いいえ垂直セグメントの数 = 1。
正方形にカットする最適な方法は次のとおりです。
1 (y から) を選択 -> 水平カット コスト = 1 × 垂直セグメント = 1
これで、水平セグメント = 2 垂直セグメント = 1 になります。
1 (y から) を選択 -> 水平カット コスト = 1 × 垂直セグメント = 1
これで、水平セグメント = 3 垂直セグメント = 1 になります。
1 (y から) を選択 -> 水平カット コスト = 1 × 垂直セグメント = 1
これで、水平セグメント = 4 垂直セグメント = 1 になります。
1 (x から) を選択 -> 垂直カット コスト = 1 × 水平セグメント = 4
これで、水平セグメント = 4 垂直セグメント = 2 になります。
1 (x から) を選択 -> 垂直カット コスト = 1 × 水平セグメント = 4
これで、水平セグメント = 4 垂直セグメント = 3 になります。
1 (x から) を選択 -> 垂直カット コスト = 1 × 水平セグメント = 4
水平セグメント = 4 垂直セグメント = 4 になりました。
したがって、合計コスト = 1 + 1 + 1 + 4 + 4 + 4 = 15 となります。

目次

[素朴なアプローチ] すべての順列を試す - O((n+m)!×(n+m)) 時間と O(n+m) 空間

このアイデアは、指定されたカットの可能なすべての順列を生成し、各順列のコストを計算することです。最後にそれらの中の最小コストを返します。

注記： 順列の数は階乗的に (m+n-2)! のように増加するため、このアプローチは入力が大きい場合には実現できません。
各順列について、O(m+n) 時間でコストを計算する必要があります。したがって、全体の時間計算量は O((m+n−2)!×(m+n)) になります。

[想定されるアプローチ] Greedy Technique を使用する - O( n (log n)+m (log m)) 時間と O(1) 空間

このアイデアは、最初に、 貪欲なアプローチ 。各ステップで最も高いコスト削減を選択すると、一度に複数の部品に影響を与えるため、将来のコストが削減されることが観察されています。垂直方向 (x) と水平方向 (y) の削減コストを降順に並べ替え、コスト削減を最大化するために大きい方を繰り返し選択します。すべてのセクションが最適に分割されるように、残りのカットは個別に処理されます。

カットすると何が起こるでしょうか？

  • 水平カット → 幅を横切ってカットするので、水平ストリップの数が増加します (hCount++)。ただし、水平カットはすべての垂直セグメントを通過する必要があるため、コストには vCount (垂直ストリップの数) が乗算されます。
  • 垂直カット → 高さを横切ってカットするので、垂直ストリップの数が増加します (vCount++)。ただし、垂直カットはすべての水平セグメントを通過する必要があるため、コストには hCount (水平ストリップの数) が乗算されます。

問題を解決する手順:

  • x 配列と y 配列の両方を降順に並べ替えます。
  • x と y に 1 つずつ 2 つのポインターを使用し、最大値から始めて小さい値に向かって移動します。
  • hCount と vCount を維持して、各カットが影響するセグメントの数を追跡し、それに応じて更新します。
  • x と y の両方に未処理のカットがある間繰り返し、常に全体的な費用を最小限に抑えるためにより大きなコストを選択します。
  • x にカットが残っている場合は、hCount 乗算器を使用して処理します。同様に、残りの y カットを vCount で処理します。
  • 次の式を使用して各ステップの合計コストを累積します: 削減コスト * 影響を受ける部品の数で、コストを最小限に抑えます。
C++ 
#include   #include #include   using namespace std; int minCost(int n int m   vector<int>& x vector<int>& y) {    // Sort the cutting costs in ascending order  sort(x.begin() x.end());  sort(y.begin() y.end());   int hCount = 1 vCount = 1;   int i = x.size() - 1 j = y.size() - 1;   int totalCost = 0;  while (i >= 0 && j >= 0) {    // Choose the larger cost cut to   // minimize future costs  if (x[i] >= y[j]) {  totalCost += x[i] * hCount;   vCount++;  i--;  }   else {  totalCost += y[j] * vCount;   hCount++;  j--;  }  }  // Process remaining vertical cuts  while (i >= 0) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  // Process remaining horizontal cuts  while (j >= 0) {  totalCost += y[j] * vCount;  hCount++;  j--;  }  return totalCost; } int main() {    int n = 4 m = 6;  vector<int> x = {2 1 3 1 4};  vector<int> y = {4 1 2};  cout << minCost(n m x y) << endl;  return 0; }
Java 
import java.util.Arrays; class GfG {    static int minCost(int n int m   int[] x int[] y) {    // Sort the cutting costs in ascending order  Arrays.sort(x);  Arrays.sort(y);   int hCount = 1 vCount = 1;   int i = x.length - 1 j = y.length - 1;   int totalCost = 0;  while (i >= 0 && j >= 0) {    // Choose the larger cost cut to   // minimize future costs  if (x[i] >= y[j]) {  totalCost += x[i] * hCount;   vCount++;  i--;  }   else {  totalCost += y[j] * vCount;   hCount++;  j--;  }  }  // Process remaining vertical cuts  while (i >= 0) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  // Process remaining horizontal cuts  while (j >= 0) {  totalCost += y[j] * vCount;  hCount++;  j--;  }  return totalCost;  }  public static void main(String[] args) {    int n = 4m = 6;  int[] x = {2 1 3 1 4};  int[] y = {4 1 2};  System.out.println(minCost(n m x y));  } }
Python 
def minCost(nm x y): # Sort the cutting costs in ascending order x.sort() y.sort() hCount vCount = 1 1 i j = len(x) - 1 len(y) - 1 totalCost = 0 while i >= 0 and j >= 0: # Choose the larger cost cut to  # minimize future costs if x[i] >= y[j]: totalCost += x[i] * hCount vCount += 1 i -= 1 else: totalCost += y[j] * vCount hCount += 1 j -= 1 # Process remaining vertical cuts while i >= 0: totalCost += x[i] * hCount vCount += 1 i -= 1 # Process remaining horizontal cuts while j >= 0: totalCost += y[j] * vCount hCount += 1 j -= 1 return totalCost if __name__ == '__main__': nm = 4 6 x = [2 1 3 1 4] y = [4 1 2] print(minCost(nmx y))
C# 
using System; class GfG {  public static int minCost(int n int m   int[] x int[] y) {    // Sort the cutting costs in ascending order  Array.Sort(x);  Array.Sort(y);  int hCount = 1 vCount = 1;  int i = x.Length - 1 j = y.Length - 1;  int totalCost = 0;  // Process the cuts in greedy manner  while (i >= 0 && j >= 0) {    // Choose the larger cost cut to   // minimize future costs  if (x[i] >= y[j]) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  else {  totalCost += y[j] * vCount;  hCount++;  j--;  }  }  // Process remaining vertical cuts  while (i >= 0) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  // Process remaining horizontal cuts  while (j >= 0) {  totalCost += y[j] * vCount;  hCount++;  j--;  }  return totalCost;  }    public static void Main() {    int n=4m=6;  int[] x = {2 1 3 1 4};  int[] y = {4 1 2};  Console.WriteLine(minCost(nm x y));  } }
JavaScript 
function minCost( nm x y) {    // Sort the cutting costs in ascending order  x.sort((a b) => a - b);  y.sort((a b) => a - b);  let hCount = 1 vCount = 1;  let i = x.length - 1 j = y.length - 1;  let totalCost = 0;  while (i >= 0 && j >= 0) {    // Choose the larger cost cut to   // minimize future costs  if (x[i] >= y[j]) {  totalCost += x[i] * hCount;  vCount++;  i--;  }   else {  totalCost += y[j] * vCount;  hCount++;  j--;  }  }  // Process remaining vertical cuts  while (i >= 0) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  // Process remaining horizontal cuts  while (j >= 0) {  totalCost += y[j] * vCount;  hCount++;  j--;  }  return totalCost; } // Driver Code let n = 4m = 6; let x = [2 1 3 1 4]; let y = [4 1 2]; console.log(minCost(nm x y));

出力 
42