Minimumskostnad for å kutte et brett i firkanter
Gitt et bord av dimensjoner n × m som må kuttes i n × m firkanter. Kostnaden for å lage et kutt langs en horisontal eller vertikal kant er gitt i to matriser:
- x[] : Kuttekostnader langs de vertikale kantene (lengdevis).
- og[] : Kutte kostnader langs de horisontale kantene (breddevis).
Finn minimum totalkostnad som kreves for å kutte brettet i firkanter optimalt.
Eksempler:
Inndata: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Produksjon: 42
Forklaring:
I utgangspunktet nei. av horisontale segmenter = 1 & nr. av vertikale segmenter = 1.
Optimal måte å kutte i firkanter er:
Velg 4 (fra x) -> vertikalt kutt Kostnad = 4 × horisontale segmenter = 4
Nå horisontale segmenter = 1 vertikale segmenter = 2.
Velg 4 (fra y) -> horisontalt kutt Kostnad = 4 × vertikale segmenter = 8
Nå horisontale segmenter = 2 vertikale segmenter = 2.
Velg 3 (fra x) -> vertikalt kutt Kostnad = 3 × horisontale segmenter = 6
Nå horisontale segmenter = 2 vertikale segmenter = 3.
Velg 2 (fra x) -> vertikalt kutt Kostnad = 2 × horisontale segmenter = 4
Nå horisontale segmenter = 2 vertikale segmenter = 4.
Velg 2 (fra y) -> horisontalt kutt Kostnad = 2 × vertikale segmenter = 8
Nå horisontale segmenter = 3 vertikale segmenter = 4.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 3
Nå horisontale segmenter = 3 vertikale segmenter = 5.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 3
Nå horisontale segmenter = 3 vertikale segmenter = 6.
Velg 1 (fra y) -> horisontalt kutt Kostnad = 1 × vertikale segmenter = 6
Nå horisontale segmenter = 4 vertikale segmenter = 6.
Så den totale kostnaden = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.Inndata: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Produksjon: 15
Forklaring:
I utgangspunktet nei. av horisontale segmenter = 1 & nr. av vertikale segmenter = 1.
Optimal måte å kutte i firkanter er:
Velg 1 (fra y) -> horisontalt kutt Kostnad = 1 × vertikale segmenter = 1
Nå horisontale segmenter = 2 vertikale segmenter = 1.
Velg 1 (fra y) -> horisontalt kutt Kostnad = 1 × vertikale segmenter = 1
Nå horisontale segmenter = 3 vertikale segmenter = 1.
Velg 1 (fra y) -> horisontalt kutt Kostnad = 1 × vertikale segmenter = 1
Nå horisontale segmenter = 4 vertikale segmenter = 1.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 4
Nå horisontale segmenter = 4 vertikale segmenter = 2.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 4
Nå horisontale segmenter = 4 vertikale segmenter = 3.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 4
Nå horisontale segmenter = 4 vertikale segmenter = 4
Så den totale kostnaden = 1 + 1 + 1 + 4 + 4 + 4 = 15.
Innholdsfortegnelse
- [Naiv tilnærming] Prøv alle permutasjoner - O((n+m)!×(n+m)) Tid og O(n+m) Mellomrom
- [Forventet tilnærming] Bruke grådig teknikk - O( n (log n)+m (log m)) Tid og O(1) Mellomrom
[Naiv tilnærming] Prøv alle permutasjoner - O((n+m)!×(n+m)) Tid og O(n+m) Mellomrom
Tanken er å generere alle mulige permutasjoner av de gitte kuttene og deretter beregne kostnadene for hver permutasjon. Til slutt returner minimumskostnaden blant dem.
Note: Denne tilnærmingen er ikke mulig for større innganger fordi antall permutasjoner vokser faktorielt som (m+n-2)!.
For hver permutasjon må vi beregne kostnaden i O(m+n) tid. Derfor blir den totale tidskompleksiteten O((m+n−2)!×(m+n)).
[Forventet tilnærming] Bruke grådig teknikk - O( n (log n)+m (log m)) Tid og O(1) Mellomrom
Tanken er å gjøre de dyreste kuttene først ved å bruke en grådig tilnærming . Observasjonen er at å velge det høyeste kostnadskuttet ved hvert trinn reduserer fremtidige kostnader ved å påvirke flere deler samtidig. Vi sorterer de vertikale (x) og horisontale (y) kuttkostnadene i synkende rekkefølge og velger iterativt den største for å maksimere kostnadsbesparelser. De resterende kuttene behandles separat for å sikre at alle seksjoner deles optimalt.
Hva skjer når vi gjør et kutt?
- Horisontalt kutt → du kutter på tvers av bredden slik at antallet horisontale strimler øker (hCount++). Men kostnaden multipliseres med vCount (antall vertikale strimler) fordi det horisontale kuttet må passere gjennom alle vertikale segmenter.
- Vertikalt kutt → du kutter på tvers av høyden slik at antallet vertikale strimler øker (vCount++). Men kostnaden multipliseres med hCount (antall horisontale strimler) fordi det vertikale kuttet må passere gjennom alle horisontale segmenter.
Trinn for å løse problemet:
- Sorter både x og y matriser i synkende rekkefølge.
- Bruk to pekere, én for x og én for y, start fra den største verdien og beveger seg mot mindre verdier.
- Oppretthold hCount og vCount for å spore hvor mange segmenter hvert kutt påvirker, og oppdater dem deretter.
- Gjenta mens både x og y har ubehandlede kutt, og velg alltid de høyere kostnadene for å minimere de totale utgiftene.
- Hvis x har gjenværende kutt, behandle dem med hCount multiplikator; behandle gjenværende y-kutt med vCount.
- Akkumuler totalkostnad ved hvert trinn ved å bruke formelen: kutt kostnad * antall berørte deler for å sikre minimal kostnad.
#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 ));
Produksjon
42Lag quiz
