Minsta kostnad för att skära en bräda i rutor
Givet en tavla av dimensioner n × m som måste skäras i n × m kvadrater. Kostnaden för att göra ett snitt längs en horisontell eller vertikal kant tillhandahålls i två arrayer:
- x[] : Skärkostnader längs de vertikala kanterna (längdmässigt).
- och[] : Skärkostnader längs de horisontella kanterna (breddmässigt).
Hitta den minsta totala kostnaden som krävs för att skära brädan i fyrkanter optimalt.
Exempel:
Input: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Produktion: 42
Förklaring:
Till en början nej. av horisontella segment = 1 & nr. av vertikala segment = 1.
Det optimala sättet att skära i kvadrat är:
Välj 4 (från x) -> vertikalt snitt Kostnad = 4 × horisontella segment = 4
Nu horisontella segment = 1 vertikala segment = 2.
Välj 4 (från y) -> horisontell skärning Kostnad = 4 × vertikala segment = 8
Nu horisontella segment = 2 vertikala segment = 2.
Välj 3 (från x) -> vertikalt snitt Kostnad = 3 × horisontella segment = 6
Nu horisontella segment = 2 vertikala segment = 3.
Välj 2 (från x) -> vertikalt snitt Kostnad = 2 × horisontella segment = 4
Nu horisontella segment = 2 vertikala segment = 4.
Välj 2 (från y) -> horisontell skärning Kostnad = 2 × vertikala segment = 8
Nu horisontella segment = 3 vertikala segment = 4.
Välj 1 (från x) -> vertikalt snitt Kostnad = 1 × horisontella segment = 3
Nu horisontella segment = 3 vertikala segment = 5.
Välj 1 (från x) -> vertikalt snitt Kostnad = 1 × horisontella segment = 3
Nu horisontella segment = 3 vertikala segment = 6.
Välj 1 (från y) -> horisontell skärning Kostnad = 1 × vertikala segment = 6
Nu horisontella segment = 4 vertikala segment = 6.
Så den totala kostnaden = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.Input: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Produktion: 15
Förklaring:
Till en början nej. av horisontella segment = 1 & nr. av vertikala segment = 1.
Det optimala sättet att skära i kvadrat är:
Välj 1 (från y) -> horisontell skärning Kostnad = 1 × vertikala segment = 1
Nu horisontella segment = 2 vertikala segment = 1.
Välj 1 (från y) -> horisontell skärning Kostnad = 1 × vertikala segment = 1
Nu horisontella segment = 3 vertikala segment = 1.
Välj 1 (från y) -> horisontell skärning Kostnad = 1 × vertikala segment = 1
Nu horisontella segment = 4 vertikala segment = 1.
Välj 1 (från x) -> vertikalt snitt Kostnad = 1 × horisontella segment = 4
Nu horisontella segment = 4 vertikala segment = 2.
Välj 1 (från x) -> vertikalt snitt Kostnad = 1 × horisontella segment = 4
Nu horisontella segment = 4 vertikala segment = 3.
Välj 1 (från x) -> vertikalt snitt Kostnad = 1 × horisontella segment = 4
Nu horisontella segment = 4 vertikala segment = 4
Så den totala kostnaden = 1 + 1 + 1 + 4 + 4 + 4 = 15.
Innehållsförteckning
- [Naiv metod] Prova alla permutationer - O((n+m)!×(n+m)) Tid och O(n+m) Mellanrum
- [Förväntad tillvägagångssätt] Använda girig teknik - O( n (log n)+m (log m)) Tid och O(1) Mellanrum
[Naiv metod] Prova alla permutationer - O((n+m)!×(n+m)) Tid och O(n+m) Mellanrum
Tanken är att generera alla möjliga permutationer av de givna nedskärningarna och sedan beräkna kostnaden för varje permutation. Äntligen returnera minimikostnaden bland dem.
Notera: Detta tillvägagångssätt är inte genomförbart för större indata eftersom antalet permutationer växer faktoriellt som (m+n-2)!.
För varje permutation måste vi beräkna kostnaden i O(m+n) tid. Därför blir den totala tidskomplexiteten O((m+n−2)!×(m+n)).
[Förväntad tillvägagångssätt] Använda girig teknik - O( n (log n)+m (log m)) Tid och O(1) Mellanrum
Tanken är att först göra de dyraste snitten med hjälp av en girigt tillvägagångssätt . Iakttagelsen är att valet av den högsta kostnadsminskningen vid varje steg minskar framtida kostnader genom att påverka flera delar samtidigt. Vi sorterar de vertikala (x) och horisontella (y) sänkningskostnaderna i fallande ordning och väljer sedan iterativt den större för att maximera kostnadsbesparingarna. De återstående snitten bearbetas separat för att säkerställa att alla sektioner delas optimalt.
Vad händer när vi gör ett snitt?
- Horisontellt snitt → du skär över bredden så att antalet horisontella remsor ökar (hCount++). Men kostnaden multipliceras med vCount (antalet vertikala remsor) eftersom det horisontella snittet måste passera genom alla vertikala segment.
- Vertikalt snitt → du skär över höjden så att antalet vertikala remsor ökar (vCount++). Men kostnaden multipliceras med hCount (antalet horisontella remsor) eftersom det vertikala snittet måste passera genom alla horisontella segment.
Steg för att lösa problemet:
- Sortera både x och y matriser i fallande ordning.
- Använd två pekare, en för x och en för y, med början från det största värdet och flytta mot mindre värden.
- Underhåll hCount och vCount för att spåra hur många segment varje klipp påverkar och uppdatera dem därefter.
- Iterera medan både x och y har obearbetade nedskärningar och välj alltid den högre kostnaden för att minimera de totala kostnaderna.
- Om x har återstående klipp bearbeta dem med hCount multiplikator; bearbeta på samma sätt återstående y-klipp med vCount.
- Ackumulera total kostnad vid varje steg med hjälp av formeln: sänka kostnaden * antal berörda stycken för att säkerställa 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 ));
Produktion
42Skapa frågesport
