Data una tavola di dimensioni n×m che deve essere tagliato in n×m quadrati. Il costo per eseguire un taglio lungo un bordo orizzontale o verticale è fornito in due categorie:

• X[] : Riduzione dei costi lungo i bordi verticali (in lunghezza).
• E[] : Riduzione dei costi lungo i bordi orizzontali (in larghezza).

Trova il costo totale minimo richiesto per tagliare il tabellone in quadrati in modo ottimale.

Esempi: 

Ingresso: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Produzione: 42
Spiegazione:

Inizialmente no. di segmenti orizzontali = 1 e n. di segmenti verticali = 1.
Il modo ottimale per tagliare in quadrato è:
Scegli 4 (da x) -> Costo taglio verticale = 4 × segmenti orizzontali = 4
 Ora segmenti orizzontali = 1 segmenti verticali = 2.
Scegli 4 (da y) -> Costo taglio orizzontale = 4 × segmenti verticali = 8
 Ora segmenti orizzontali = 2 segmenti verticali = 2.
Scegli 3 (da x) -> Costo taglio verticale = 3 × segmenti orizzontali = 6
 Ora segmenti orizzontali = 2 segmenti verticali = 3.
Scegli 2 (da x) -> Costo taglio verticale = 2 × segmenti orizzontali = 4
 Ora segmenti orizzontali = 2 segmenti verticali = 4.
Scegli 2 (da y) -> Costo taglio orizzontale = 2 × segmenti verticali = 8
 Ora segmenti orizzontali = 3 segmenti verticali = 4.
Scegli 1 (da x) -> Costo taglio verticale = 1 × segmenti orizzontali = 3
Ora segmenti orizzontali = 3 segmenti verticali = 5.
Scegli 1 (da x) -> Costo taglio verticale = 1 × segmenti orizzontali = 3
Ora segmenti orizzontali = 3 segmenti verticali = 6.
Scegli 1 (da y) -> Costo taglio orizzontale = 1 × segmenti verticali = 6
Ora segmenti orizzontali = 4 segmenti verticali = 6.
Quindi il costo totale = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

Ingresso: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Produzione: 15
Spiegazione:
Inizialmente no. di segmenti orizzontali = 1 e n. di segmenti verticali = 1.
Il modo ottimale per tagliare in quadrato è:
Scegli 1 (da y) -> Costo taglio orizzontale = 1 × segmenti verticali = 1
Ora segmenti orizzontali = 2 segmenti verticali = 1.
Scegli 1 (da y) -> Costo taglio orizzontale = 1 × segmenti verticali = 1
Ora segmenti orizzontali = 3 segmenti verticali = 1.
Scegli 1 (da y) -> Costo taglio orizzontale = 1 × segmenti verticali = 1
Ora segmenti orizzontali = 4 segmenti verticali = 1.
Scegli 1 (da x) -> Costo taglio verticale = 1 × segmenti orizzontali = 4
Ora segmenti orizzontali = 4 segmenti verticali = 2.
Scegli 1 (da x) -> Costo taglio verticale = 1 × segmenti orizzontali = 4
Ora segmenti orizzontali = 4 segmenti verticali = 3.
Scegli 1 (da x) -> Costo taglio verticale = 1 × segmenti orizzontali = 4
Ora segmenti orizzontali = 4 segmenti verticali = 4
Quindi il costo totale = 1 + 1 + 1 + 4 + 4 + 4 = 15.

Sommario

• [Approccio ingenuo] Prova tutte le permutazioni: O((n+m)!×(n+m)) Tempo e O(n+m) Spazio
• [Approccio previsto] Utilizzo della tecnica Greedy - O( n (log n)+m (log m)) Tempo e O(1) Spazio

[Approccio ingenuo] Prova tutte le permutazioni: O((n+m)!×(n+m)) Tempo e O(n+m) Spazio

L'idea è di generare tutte le possibili permutazioni dei tagli dati e quindi calcolare il costo per ciascuna permutazione. Infine restituire il costo minimo tra di loro.

Nota: Questo approccio non è fattibile per input più grandi perché il numero di permutazioni cresce fattorialmente come (m+n-2)!.
Per ogni permutazione dobbiamo calcolare il costo in tempo O(m+n). Quindi la complessità temporale complessiva diventa O((m+n−2)!×(m+n)).

[Approccio previsto] Utilizzo della tecnica Greedy - O( n (log n)+m (log m)) Tempo e O(1) Spazio

L'idea è di effettuare prima i tagli più costosi utilizzando a approccio avido . L’osservazione è che la scelta del taglio di costo più elevato in ogni fase riduce i costi futuri incidendo su più pezzi contemporaneamente. Ordiniamo i costi di taglio verticale (x) e orizzontale (y) in ordine decrescente, quindi scegliamo iterativamente quello più grande per massimizzare il risparmio sui costi. I tagli rimanenti vengono elaborati separatamente per garantire che tutte le sezioni siano divise in modo ottimale.

Cosa succede quando effettuiamo un taglio?

• Taglio orizzontale → stai tagliando lungo la larghezza in modo che il numero di strisce orizzontali aumenti (hCount++). Ma il costo viene moltiplicato per vCount (il numero di strisce verticali) perché il taglio orizzontale deve passare attraverso tutti i segmenti verticali.
• Taglio verticale → stai tagliando in altezza in modo che il numero di strisce verticali aumenti (vCount++). Ma il costo viene moltiplicato per hCount (il numero di strisce orizzontali) perché il taglio verticale deve passare attraverso tutti i segmenti orizzontali.

Passaggi per risolvere il problema:

• Ordina sia gli array x che quelli y in ordine decrescente.
• Utilizza due puntatori, uno per x e uno per y, partendo dal valore più grande e spostandosi verso valori più piccoli.
• Mantieni hCount e vCount per monitorare il numero di segmenti interessati da ciascun taglio e aggiornarli di conseguenza.
• Ripeti l'iterazione mentre sia x che y hanno tagli non elaborati, scegliendo sempre il costo maggiore per ridurre al minimo le spese complessive.
• Se x ha dei tagli rimanenti, elaborali con il moltiplicatore hCount; allo stesso modo elabora i tagli y rimanenti con vCount.
• Accumula il costo totale in ogni passaggio utilizzando la formula: riduci i costi * numero di pezzi interessati garantendo un costo minimo.

#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; } 

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));  } } 

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)) 

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));  } } 

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