Donat un tauler de dimensions n × m que s'ha de tallar en n × m quadrats. El cost de fer un tall al llarg d'una vora horitzontal o vertical es proporciona en dues matrius:
- x[] : Reducció de costos al llarg de les vores verticals (en sentit longitudinal).
- i[] : Reducció de costos al llarg de les vores horitzontals (ample).
Trobeu el cost total mínim necessari per tallar el tauler en quadrats de manera òptima.
Exemples:
Entrada: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Sortida: 42
Explicació:
Inicialment no. de segments horitzontals = 1 & núm. de segments verticals = 1.
La manera òptima de tallar en quadrats és:
Trieu 4 (de x) -> tall vertical Cost = 4 × segments horitzontals = 4
Ara segments horitzontals = 1 segments verticals = 2.
Trieu 4 (de y) -> tall horitzontal Cost = 4 × segments verticals = 8
Ara segments horitzontals = 2 segments verticals = 2.
Trieu 3 (de x) -> tall vertical Cost = 3 × segments horitzontals = 6
Ara segments horitzontals = 2 segments verticals = 3.
Trieu 2 (de x) -> tall vertical Cost = 2 × segments horitzontals = 4
Ara segments horitzontals = 2 segments verticals = 4.
Trieu 2 (de y) -> tall horitzontal Cost = 2 × segments verticals = 8
Ara segments horitzontals = 3 segments verticals = 4.
Trieu 1 (de x) -> tall vertical Cost = 1 × segments horitzontals = 3
Ara segments horitzontals = 3 segments verticals = 5.
Trieu 1 (de x) -> tall vertical Cost = 1 × segments horitzontals = 3
Ara segments horitzontals = 3 segments verticals = 6.
Trieu 1 (de y) -> tall horitzontal Cost = 1 × segments verticals = 6
Ara segments horitzontals = 4 segments verticals = 6.
Per tant, el cost total = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.Entrada: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Sortida: 15
Explicació:
Inicialment no. de segments horitzontals = 1 & núm. de segments verticals = 1.
La manera òptima de tallar en quadrats és:
Trieu 1 (de y) -> tall horitzontal Cost = 1 × segments verticals = 1
Ara segments horitzontals = 2 segments verticals = 1.
Trieu 1 (de y) -> tall horitzontal Cost = 1 × segments verticals = 1
Ara segments horitzontals = 3 segments verticals = 1.
Trieu 1 (de y) -> tall horitzontal Cost = 1 × segments verticals = 1
Ara segments horitzontals = 4 segments verticals = 1.
Trieu 1 (de x) -> tall vertical Cost = 1 × segments horitzontals = 4
Ara segments horitzontals = 4 segments verticals = 2.
Trieu 1 (de x) -> tall vertical Cost = 1 × segments horitzontals = 4
Ara segments horitzontals = 4 segments verticals = 3.
Trieu 1 (de x) -> tall vertical Cost = 1 × segments horitzontals = 4
Ara segments horitzontals = 4 segments verticals = 4
Per tant, el cost total = 1 + 1 + 1 + 4 + 4 + 4 = 15.
Taula de continguts
- [Enfocament ingenu] Proveu totes les permutacions - O((n+m)!×(n+m)) Temps i O(n+m) Espai
- [Enfocament esperat] Ús de la tècnica Greedy - O( n (log n) + m (log m)) Temps i O (1) espai
[Enfocament ingenu] Proveu totes les permutacions - O((n+m)!×(n+m)) Temps i O(n+m) Espai
La idea és generar totes les permutacions possibles dels talls donats i després calcular el cost de cada permutació. Finalment retornar el cost mínim entre ells.
Nota: Aquest enfocament no és factible per a entrades més grans perquè el nombre de permutacions creix factorialment com (m+n-2)!.
Per a cada permutació hem de calcular el cost en temps O(m+n). Per tant, la complexitat temporal global esdevé O((m+n−2)!×(m+n)).
[Enfocament esperat] Ús de la tècnica Greedy - O( n (log n) + m (log m)) Temps i O (1) espai
La idea és fer primer les retallades més cares utilitzant a enfocament cobdiciós . L'observació és que escollir la reducció de costos més alta a cada pas redueix els costos futurs en afectar diverses peces alhora. Ordenem els costos verticals (x) i horitzontals (y) reduïts en ordre descendent i després triem iterativament el més gran per maximitzar l'estalvi de costos. Els talls restants es processen per separat per garantir que totes les seccions es divideixen de manera òptima.
Què passa quan fem un tall?
- Tall horitzontal → esteu tallant l'amplada de manera que augmenta el nombre de tires horitzontals (hCount++). Però el cost es multiplica per vCount (el nombre de tires verticals) perquè el tall horitzontal ha de passar per tots els segments verticals.
- Tall vertical → esteu tallant l'alçada de manera que el nombre de tires verticals augmenta (vCount++). Però el cost es multiplica per hCount (el nombre de tires horitzontals) perquè el tall vertical ha de passar per tots els segments horitzontals.
Passos per resoldre el problema:
- Ordena les matrius x i y en ordre descendent.
- Fes servir dos punters un per x i un per y començant pel valor més gran i avançant cap a valors més petits.
- Manteniu hCount i vCount per fer un seguiment de quants segments afecta cada tall i actualitzar-los en conseqüència.
- Itereu mentre que x i y tinguin retallades sense processar sempre escollint el cost més per minimitzar les despeses generals.
- Si x li queden talls processeu-los amb hCount multiplicador; De la mateixa manera, processeu els retalls i restants amb vCount.
- Acumuleu cost total a cada pas mitjançant la fórmula: reduïu el cost * nombre de peces afectades per garantir un cost mínim.
#include
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));
Sortida
42