Costo minimo per tagliare una tavola in quadrati
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 ; }
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 = 4 m = 6 ; int [] x = { 2 1 3 1 4 }; int [] y = { 4 1 2 }; System . out . println ( minCost ( n m x y )); } }
Python def minCost ( n m 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__' : n m = 4 6 x = [ 2 1 3 1 4 ] y = [ 4 1 2 ] print ( minCost ( n m x 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 = 4 m = 6 ; int [] x = { 2 1 3 1 4 }; int [] y = { 4 1 2 }; Console . WriteLine ( minCost ( n m x y )); } }
JavaScript function minCost ( n m 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 = 4 m = 6 ; let x = [ 2 1 3 1 4 ]; let y = [ 4 1 2 ]; console . log ( minCost ( n m x y ));
Produzione
42Crea quiz
