Custo mínimo para cortar um tabuleiro em quadrados
Dada uma placa de dimensões n × m que precisa ser cortado em quadrados n × m. O custo de fazer um corte ao longo de uma borda horizontal ou vertical é fornecido em duas matrizes:
- x[] : Corte de custos ao longo das bordas verticais (longitudinalmente).
- e[] : Corte de custos ao longo das bordas horizontais (em largura).
Encontre o custo total mínimo necessário para cortar o tabuleiro em quadrados de maneira ideal.
Exemplos:
Entrada: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Saída: 42
Explicação:
Inicialmente não. de segmentos horizontais = 1 e não. de segmentos verticais = 1.
A maneira ideal de cortar em quadrado é:
Escolha 4 (de x) -> corte vertical Custo = 4 × segmentos horizontais = 4
Agora segmentos horizontais = 1 segmentos verticais = 2.
Escolha 4 (de y) -> corte horizontal Custo = 4 × segmentos verticais = 8
Agora segmentos horizontais = 2 segmentos verticais = 2.
Escolha 3 (de x) -> corte vertical Custo = 3 × segmentos horizontais = 6
Agora segmentos horizontais = 2 segmentos verticais = 3.
Escolha 2 (de x) -> corte vertical Custo = 2 × segmentos horizontais = 4
Agora segmentos horizontais = 2 segmentos verticais = 4.
Escolha 2 (de y) -> corte horizontal Custo = 2 × segmentos verticais = 8
Agora segmentos horizontais = 3 segmentos verticais = 4.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 3
Agora segmentos horizontais = 3 segmentos verticais = 5.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 3
Agora segmentos horizontais = 3 segmentos verticais = 6.
Escolha 1 (de y) -> corte horizontal Custo = 1 × segmentos verticais = 6
Agora segmentos horizontais = 4 segmentos verticais = 6.
Portanto, o custo total = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.Entrada: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Saída: 15
Explicação:
Inicialmente não. de segmentos horizontais = 1 e não. de segmentos verticais = 1.
A maneira ideal de cortar em quadrado é:
Escolha 1 (de y) -> corte horizontal Custo = 1 × segmentos verticais = 1
Agora segmentos horizontais = 2 segmentos verticais = 1.
Escolha 1 (de y) -> corte horizontal Custo = 1 × segmentos verticais = 1
Agora segmentos horizontais = 3 segmentos verticais = 1.
Escolha 1 (de y) -> corte horizontal Custo = 1 × segmentos verticais = 1
Agora segmentos horizontais = 4 segmentos verticais = 1.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 4
Agora segmentos horizontais = 4 segmentos verticais = 2.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 4
Agora segmentos horizontais = 4 segmentos verticais = 3.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 4
Agora segmentos horizontais = 4 segmentos verticais = 4
Portanto, o custo total = 1 + 1 + 1 + 4 + 4 + 4 = 15.
Índice
- [Abordagem ingênua] Experimente todas as permutações - O((n+m)!×(n+m)) Tempo e O(n+m) Espaço
- [Abordagem esperada] Usando técnica gananciosa - O( n (log n)+m (log m)) Tempo e O(1) Espaço
[Abordagem ingênua] Experimente todas as permutações - O((n+m)!×(n+m)) Tempo e O(n+m) Espaço
A ideia é gerar todas as permutações possíveis dos cortes fornecidos e depois calcular o custo de cada permutação. Por fim, retorne o custo mínimo entre eles.
Observação: Esta abordagem não é viável para entradas maiores porque o número de permutações cresce fatorialmente como (m+n-2)!.
Para cada permutação devemos calcular o custo em tempo O(m+n). Conseqüentemente, a complexidade geral do tempo torna-se O((m+n−2)!×(m+n)).
[Abordagem esperada] Usando técnica gananciosa - O( n (log n)+m (log m)) Tempo e O(1) Espaço
A ideia é fazer primeiro os cortes mais caros usando um abordagem gananciosa . A observação é que escolher o maior corte de custos em cada etapa reduz os custos futuros ao afetar várias peças ao mesmo tempo. Classificamos os custos de corte vertical (x) e horizontal (y) em ordem decrescente e, em seguida, escolhemos iterativamente o maior para maximizar a economia de custos. Os cortes restantes são processados separadamente para garantir que todas as seções sejam divididas de maneira ideal.
O que acontece quando fazemos um corte?
- Corte horizontal → você está cortando na largura para que o número de faixas horizontais aumente (hCount++). Mas o custo é multiplicado por vCount (o número de tiras verticais) porque o corte horizontal tem que passar por todos os segmentos verticais.
- Corte vertical → você está cortando na altura para que o número de faixas verticais aumente (vCount++). Mas o custo é multiplicado por hCount (o número de faixas horizontais) porque o corte vertical tem que passar por todos os segmentos horizontais.
Passos para resolver o problema:
- Classifique as matrizes x e y em ordem decrescente.
- Use dois ponteiros, um para x e outro para y, começando do valor maior e avançando em direção a valores menores.
- Mantenha hCount e vCount para rastrear quantos segmentos cada corte afeta e atualizá-los adequadamente.
- Itere enquanto x e y têm cortes não processados, sempre escolhendo o custo maior para minimizar as despesas gerais.
- Se x tiver cortes restantes, processe-os com o multiplicador hCount; da mesma forma, processe os cortes restantes com vCount.
- Acumule o custo total em cada etapa usando a fórmula: corte de custo * número de peças afetadas garantindo custo mínimo.
#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 ));
Saída
42Criar questionário
