Papir skåret i minimum antal firkanter
Givet et rektangulært papir af dimensioner a x b . Opgaven er at skære hele papiret i minimum antal firkant stykker. Vi kan vælge firkantede stykker af enhver størrelse, men de skal skæres uden at overlappe eller efterlade ekstra plads .
Eksempler:
Input: a = 5 b = 8
5 firkanter skåret af papir i størrelsen 5 X 8
Produktion: 5
Forklaring: Vi kan skære papiret i 5 kvadrater: 1 kvadrat i størrelsen 5x5 1 kvadrat med størrelsen 3x3 1 kvadrat med størrelsen 2x2 og 2 kvadrater i størrelsen 1x1.Input: a = 13 b = 11
6 firkanter skåret af papir i størrelsen 13 X 11
Produktion: 6
Forklaring: Vi kan skære papiret i 6 kvadrater: 1 kvadrat med størrelsen 7x7 1 kvadrat med størrelsen 6x6 1 kvadrat med størrelsen 5x5 2 kvadrater af størrelsen 4x4 og 1 kvadrat med størrelsen 1x1.Input: a = 6 b = 7
5 firkanter skåret af papir i størrelsen 6 X 7
Produktion: 5
Forklaring: Vi kan skære papiret i 5 firkanter: 1 firkant i størrelsen 4x4 2 firkanter i størrelsen 3x3 og 2 firkanter i størrelsen 3x3.
5 firkanter skåret af papir i størrelsen 5 X 8 
6 firkanter skåret af papir i størrelsen 13 X 11 
5 firkanter skåret af papir i størrelsen 6 X 7 Indholdsfortegnelse
- [Forkert tilgang 1] Brug af grådig teknik
- [Forkert tilgang 2] Brug af dynamisk programmering
- [Korrekt tilgang] Brug af DFS og dynamisk programmering
[Forkert tilgang 1] Brug af grådig teknik
Ved første øjekast kan det se ud til, at problemet let kan løses ved at skære den størst mulige firkant fra papiret først efterfulgt af at skære den største firkant fra det resterende papir og så videre, indtil vi har klippet hele papiret. Men denne løsning er forkert.
Hvorfor Greedy Approach virker ikke?
Overvej et papir af størrelse 6x7 så hvis vi forsøger at skære i papiret grådigt, får vi 7 firkanter: 1 kvadrat af størrelse 6x6 og 6 kvadrater af størrelse 1x1 hvorimod den korrekte løsning er: 5. Derfor vil grådig tilgang ikke fungere.
[Forkert tilgang 2] Brug af dynamisk programmering
Dynamisk programmering med lodrette eller horisontale snit: En anden løsning, der kan virke korrekt, er at bruge Dynamisk programmering . Vi kan vedligeholde en dp[][] tabel sådan, at dp[i][j] = minimum antal firkanter, der kan klippes af papir af størrelse i x j . Så til papir af størrelse axb
- Vi kan prøve at skære det langs hver række: dp[i][j] = min(dp[i][j] 1 + dp[i - k][j] + dp[k][j]) hvor k kan være i området [1 i - 1].
- Vi kan prøve at skære det langs hver kolonne: dp[i][j] = min(dp[i][j] 1 + dp[i][j - k] + dp[i][k]) hvor k kan være i området [1 j - 1].
Endelig vil minimum af alle nedskæringer være svaret. Men denne løsning er også forkert.
Hvorfor vil det ikke fungere at skære lodret eller vandret med Dynamic Programming Approach?
Dette vil ikke fungere, fordi vi antager, at et lodret eller vandret snit altid vil opdele rektanglet i to dele. Overvej et papir af størrelse 13x11 så hvis vi prøver at klippe papiret ved hjælp af DP-metoden, får vi 8 kvadrater, men det rigtige svar (som vist i eksemplerne) er 6. Derfor virker dynamisk programmering ikke.
[Korrekt tilgang] Brug af DFS og dynamisk programmering
C++De ide er at skære hele papiret vha DFS i nedefra og op måde. I hvert trin skal du finde det nederste venstre hjørne af papiret og prøve at skære firkanter af alle mulige størrelser fra det hjørne. Når du har skåret en firkant igen, skal du finde det nederste venstre hjørne af det resterende papir for at skære firkanter i alle mulige størrelser og så videre. Men hvis vi prøver alle mulige klip fra det nederste venstre hjørne af alle mulige papirstørrelser, så ville det være ret ineffektivt. Vi kan optimere det ved at bruge Dynamisk programmering at gemme minimumssnit for hver mulig papirstørrelse.
For entydigt at identificere enhver papirstørrelse kan vi opretholde et remSq[]-array, således at remSq[i] gemmer antallet af resterende kvadrater med størrelsen 1x1 i papirets ite kolonne. Så for et papir i størrelsen 6x7 remSq[] = {6 6 6 6 6 6 6}. For også at finde det nederste venstre hjørne finder vi det første indeks med de maksimale resterende kvadrater. Så vi kan hash værdien af remSq[] array for at finde en unik nøgle til alle de mulige værdier af remSq[] array.
// C++ Program to find minimum number of squares to cut // from a paper of size axb #include using namespace std ; // function to get the hash key for remSq array int getKey ( vector < int > & remSq int b ) { int base = 1 ; int key = 0 ; for ( int i = 0 ; i < b ; i ++ ) { key += ( remSq [ i ] * base ); base = base * ( b + 1 ); } return key ; } // Recursive function to find the minimum number of square cuts // for a given remSq array int minCutUtil ( vector < int > & remSq int a int b map < int int > & memo ) { // pointers to mark the start and end of range // with maximum remaining squares int start end ; // Check if we have previously calculated the answer // for the same state int key = getKey ( remSq b ); if ( memo . find ( key ) != memo . end ()) return memo [ key ]; int maxRemSq = 0 ; // Find the starting point of min height for ( int i = 0 ; i < b ; i ++ ) { if ( remSq [ i ] > maxRemSq ) { maxRemSq = remSq [ i ]; start = i ; } } // If max remaining squares = 0 then we have already // cut the entire paper if ( maxRemSq == 0 ) return 0 ; end = start ; vector < int > newRemSq = remSq ; int ans = INT_MAX ; // Find the ending point of min height while ( end < b ) { // length of edge of square from start till current end int squareEdge = end - start + 1 ; // If the current column does not have maximum remaining // squares or if it's impossible to cut a square of // size squareEdge then break out of the loop if ( newRemSq [ end ] != maxRemSq || newRemSq [ end ] - squareEdge < 0 ) break ; // If we can cut a square of size squareEdge // update the remainingSquares for ( int i = start ; i <= end ; i ++ ) newRemSq [ i ] = maxRemSq - squareEdge ; // Find the solution for new remainingSquares ans = min ( ans 1 + minCutUtil ( newRemSq a b memo )); end += 1 ; } return memo [ key ] = ans ; } // Function to find the minimum number of squares we can cut // using paper of size a X b int minCut ( int a int b ) { // if the given rectangle is a square if ( a == b ) return 1 ; // Initialize remaining squares = a for all the b columns vector < int > remSq ( b a ); map < int int > memo ; return minCutUtil ( remSq a b memo ); } int main () { // Sample Input int a = 13 b = 11 ; // Function call to get minimum number // of squares for axb cout < < minCut ( a b ); return 0 ; }
Java // Java Program to find minimum number of squares to cut // from a paper of size axb import java.util.* ; class GfG { // function to get the hash key for remSq array static int getKey ( int [] remSq int b ) { int base = 1 ; int key = 0 ; for ( int i = 0 ; i < b ; i ++ ) { key += ( remSq [ i ] * base ); base = base * ( b + 1 ); } return key ; } // Recursive function to find the minimum number of square cuts // for a given remSq array static int minCutUtil ( int [] remSq int a int b Map < Integer Integer > memo ) { // pointers to mark the start and end of range // with maximum remaining squares int start = 0 end ; // Check if we have previously calculated the answer // for the same state int key = getKey ( remSq b ); if ( memo . containsKey ( key )) return memo . get ( key ); int maxRemSq = 0 ; // Find the starting point of min height for ( int i = 0 ; i < b ; i ++ ) { if ( remSq [ i ] > maxRemSq ) { maxRemSq = remSq [ i ] ; start = i ; } } // If max remaining squares = 0 then we have already // cut the entire paper if ( maxRemSq == 0 ) return 0 ; end = start ; int [] newRemSq = Arrays . copyOf ( remSq b ); int ans = Integer . MAX_VALUE ; // Find the ending point of min height while ( end < b ) { // length of edge of square from start till current end int squareEdge = end - start + 1 ; // If the current column does not have maximum remaining // squares or if it's impossible to cut a square of // size squareEdge then break out of the loop if ( newRemSq [ end ] != maxRemSq || newRemSq [ end ] - squareEdge < 0 ) break ; // If we can cut a square of size squareEdge // update the remainingSquares for ( int i = start ; i <= end ; i ++ ) newRemSq [ i ] = maxRemSq - squareEdge ; // Find the solution for new remainingSquares ans = Math . min ( ans 1 + minCutUtil ( newRemSq a b memo )); end += 1 ; } memo . put ( key ans ); return ans ; } // Function to find the minimum number of squares we can cut // using paper of size a X b static int minCut ( int a int b ) { // if the given rectangle is a square if ( a == b ) return 1 ; // Initialize remaining squares = a for all the b columns int [] remSq = new int [ b ] ; Arrays . fill ( remSq a ); Map < Integer Integer > memo = new HashMap <> (); return minCutUtil ( remSq a b memo ); } public static void main ( String [] args ) { // Sample Input int a = 13 b = 11 ; // Function call to get minimum number // of squares for axb System . out . println ( minCut ( a b )); } }
Python # Python Program to find minimum number of squares to cut # from a paper of size axb # function to get the hash key for remSq array def getKey ( remSq b ): base = 1 key = 0 for i in range ( b ): key += remSq [ i ] * base base = base * ( b + 1 ) return key # Recursive function to find the minimum number of square cuts # for a given remSq array def minCutUtil ( remSq a b memo ): # pointers to mark the start and end of range # with maximum remaining squares start = 0 # Check if we have previously calculated the answer # for the same state key = getKey ( remSq b ) if key in memo : return memo [ key ] maxRemSq = 0 # Find the starting point of min height for i in range ( b ): if remSq [ i ] > maxRemSq : maxRemSq = remSq [ i ] start = i # If max remaining squares = 0 then we have already # cut the entire paper if maxRemSq == 0 : return 0 end = start newRemSq = remSq [:] ans = float ( 'inf' ) # Find the ending point of min height while end < b : # length of edge of square from start till current end squareEdge = end - start + 1 # If the current column does not have maximum remaining # squares or if it's impossible to cut a square of # size squareEdge then break out of the loop if newRemSq [ end ] != maxRemSq or newRemSq [ end ] - squareEdge < 0 : break # If we can cut a square of size squareEdge # update the remainingSquares for i in range ( start end + 1 ): newRemSq [ i ] = maxRemSq - squareEdge # Find the solution for new remainingSquares ans = min ( ans 1 + minCutUtil ( newRemSq a b memo )) end += 1 memo [ key ] = ans return ans # Function to find the minimum number of squares we can cut # using paper of size a X b def minCut ( a b ): # if the given rectangle is a square if a == b : return 1 # Initialize remaining squares = a for all the b columns remSq = [ a ] * b memo = {} return minCutUtil ( remSq a b memo ) if __name__ == '__main__' : # Sample Input a = 13 b = 11 # Function call to get minimum number # of squares for axb print ( minCut ( a b ))
C# // C# Program to find minimum number of squares to cut // from a paper of size axb using System ; using System.Collections.Generic ; class GfG { // function to get the hash key for remSq array static int getKey ( int [] remSq int b ) { int baseVal = 1 ; int key = 0 ; for ( int i = 0 ; i < b ; i ++ ) { key += ( remSq [ i ] * baseVal ); baseVal = baseVal * ( b + 1 ); } return key ; } // Recursive function to find the minimum number of square cuts // for a given remSq array static int minCutUtil ( int [] remSq int a int b Dictionary < int int > memo ) { // pointers to mark the start and end of range // with maximum remaining squares int start = 0 end ; // Check if we have previously calculated the answer // for the same state int key = getKey ( remSq b ); if ( memo . ContainsKey ( key )) return memo [ key ]; int maxRemSq = 0 ; // Find the starting point of min height for ( int i = 0 ; i < b ; i ++ ) { if ( remSq [ i ] > maxRemSq ) { maxRemSq = remSq [ i ]; start = i ; } } // If max remaining squares = 0 then we have already // cut the entire paper if ( maxRemSq == 0 ) return 0 ; end = start ; int [] newRemSq = ( int []) remSq . Clone (); int ans = int . MaxValue ; // Find the ending point of min height while ( end < b ) { // length of edge of square from start till current end int squareEdge = end - start + 1 ; // If the current column does not have maximum remaining // squares or if it's impossible to cut a square of // size squareEdge then break out of the loop if ( newRemSq [ end ] != maxRemSq || newRemSq [ end ] - squareEdge < 0 ) break ; // If we can cut a square of size squareEdge // update the remainingSquares for ( int i = start ; i <= end ; i ++ ) newRemSq [ i ] = maxRemSq - squareEdge ; // Find the solution for new remainingSquares ans = Math . Min ( ans 1 + minCutUtil ( newRemSq a b memo )); end += 1 ; } memo [ key ] = ans ; return ans ; } // Function to find the minimum number of squares we can cut // using paper of size a X b static int minCut ( int a int b ) { // if the given rectangle is a square if ( a == b ) return 1 ; // Initialize remaining squares = a for all the b columns int [] remSq = new int [ b ]; for ( int i = 0 ; i < b ; i ++ ) remSq [ i ] = a ; Dictionary < int int > memo = new Dictionary < int int > (); return minCutUtil ( remSq a b memo ); } static void Main () { int a = 13 b = 11 ; // Function call to get minimum number // of squares for axb Console . WriteLine ( minCut ( a b )); } }
JavaScript // JavaScript Program to find minimum number of squares to cut // from a paper of size axb // function to get the hash key for remSq array function getKey ( remSq b ) { let base = 1 ; let key = 0 ; for ( let i = 0 ; i < b ; i ++ ) { key += ( remSq [ i ] * base ); base = base * ( b + 1 ); } return key ; } // Recursive function to find the minimum number of square cuts // for a given remSq array function minCutUtil ( remSq a b memo ) { // pointers to mark the start and end of range // with maximum remaining squares let start = 0 end ; // Check if we have previously calculated the answer // for the same state let key = getKey ( remSq b ); if ( key in memo ) return memo [ key ]; let maxRemSq = 0 ; // Find the starting point of min height for ( let i = 0 ; i < b ; i ++ ) { if ( remSq [ i ] > maxRemSq ) { maxRemSq = remSq [ i ]; start = i ; } } // If max remaining squares = 0 then we have already // cut the entire paper if ( maxRemSq === 0 ) return 0 ; end = start ; let newRemSq = remSq . slice (); let ans = Infinity ; // Find the ending point of min height while ( end < b ) { // length of edge of square from start till current end let squareEdge = end - start + 1 ; // If the current column does not have maximum remaining // squares or if it's impossible to cut a square of // size squareEdge then break out of the loop if ( newRemSq [ end ] !== maxRemSq || newRemSq [ end ] - squareEdge < 0 ) break ; // If we can cut a square of size squareEdge // update the remainingSquares for ( let i = start ; i <= end ; i ++ ) newRemSq [ i ] = maxRemSq - squareEdge ; // Find the solution for new remainingSquares ans = Math . min ( ans 1 + minCutUtil ( newRemSq a b memo )); end += 1 ; } memo [ key ] = ans ; return ans ; } // Function to find the minimum number of squares we can cut // using paper of size a X b function minCut ( a b ) { // if the given rectangle is a square if ( a === b ) return 1 ; // Initialize remaining squares = a for all the b columns let remSq = new Array ( b ). fill ( a ); let memo = {}; return minCutUtil ( remSq a b memo ); } // Driver Code let a = 13 b = 11 ; // Function call to get minimum number // of squares for axb console . log ( minCut ( a b ));
Produktion
6
Tidskompleksitet: O(a^b) for hver af b kolonner kan vi have a kvadrater.
Hjælpeplads: O(a^b) på grund af memoization, der lagrer hver unik tilstand.
