Papir kuttet i minimum antall firkanter
Gitt et rektangulært papir av dimensjoner a x b . Oppgaven er å kutte hele papiret i minimum antall kvadrat stykker. Vi kan velge firkantede stykker i alle størrelser, men de må kuttes uten å overlappe eller etterlate ekstra plass .
Eksempler:
Inndata: a = 5 b = 8
5 firkanter kuttet fra papir i størrelse 5 X 8
Produksjon: 5
Forklaring: Vi kan kutte papiret i 5 ruter: 1 kvadrat i størrelsen 5x5 1 kvadrat i størrelsen 3x3 1 kvadrat i størrelsen 2x2 og 2 kvadrater i størrelsen 1x1.Inndata: a = 13 b = 11
6 firkanter kuttet fra papir i størrelse 13 X 11
Produksjon: 6
Forklaring: Vi kan kutte papiret i 6 ruter: 1 kvadrat med størrelse 7x7 1 kvadrat med størrelse 6x6 1 kvadrat med størrelse 5x5 2 kvadrater i størrelse 4x4 og 1 kvadrat med størrelse 1x1.Inndata: a = 6 b = 7
5 firkanter kuttet fra papir i størrelse 6 X 7
Produksjon: 5
Forklaring: Vi kan kutte papiret i 5 ruter: 1 kvadrat i størrelsen 4x4 2 ruter i størrelsen 3x3 og 2 ruter i størrelsen 3x3.
5 firkanter kuttet fra papir i størrelse 5 X 8 
6 firkanter kuttet fra papir i størrelse 13 X 11 
5 firkanter kuttet fra papir i størrelse 6 X 7 Innholdsfortegnelse
- [Feil tilnærming 1] Bruke grådig teknikk
- [Feil tilnærming 2] Bruke dynamisk programmering
- [Riktig tilnærming] Bruke DFS og dynamisk programmering
[Feil tilnærming 1] Bruke grådig teknikk
Ved første øyekast kan det virke som om problemet lett kan løses ved å kutte den største firkanten fra papiret først, etterfulgt av å kutte den største firkanten fra det gjenværende papiret og så videre til vi har kuttet hele papiret. Men denne løsningen er feil.
Hvorfor Greedy Approach vil ikke fungere?
Vurder et papir av størrelse 6x7 så hvis vi prøver å kutte papiret grådig, får vi det 7 firkanter: 1 kvadrat av størrelse 6x6 og 6 kvadrater i størrelse 1x1 mens den riktige løsningen er: 5. Derfor vil grådig tilnærming ikke fungere.
[Feil tilnærming 2] Bruke dynamisk programmering
Dynamisk programmering med vertikale eller horisontale kutt: En annen løsning som kan virke riktig er å bruke Dynamisk programmering . Vi kan opprettholde en dp[][]-tabell slik at dp[i][j] = minimum antall firkanter som kan kuttes fra papir av størrelse i x j . Så for papir i størrelse axb
- Vi kan prøve å kutte den langs hver rad: 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 å kutte den 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].
Til slutt vil minimum av alle kutt være svaret. Men denne løsningen er også feil.
Hvorfor vil det ikke fungere å kutte vertikalt eller horisontalt med Dynamic Programming Approach?
Dette vil ikke fungere fordi vi antar at et vertikalt eller horisontalt snitt alltid vil dele rektangelet i to deler. Vurder et papir av størrelse 13x11 så hvis vi prøver å kutte papiret ved hjelp av DP-tilnærming, vil vi få 8 ruter, men det riktige svaret (som vist i eksempler) er 6. Derfor vil ikke dynamisk programmering fungere.
[Riktig tilnærming] Bruke DFS og dynamisk programmering
C++De idé er å kutte hele papiret ved hjelp av DFS i nedenfra og opp måte. I hvert trinn finner du det nederste venstre hjørnet av papiret og prøv å kutte firkanter i alle mulige størrelser fra det hjørnet. Etter å ha kuttet en firkant igjen, finn det nederste venstre hjørnet av det gjenværende papiret for å kutte firkanter i alle mulige størrelser og så videre. Men hvis vi prøver alle mulige kutt fra det nederste venstre hjørnet av alle mulige papirstørrelser, vil det være ganske ineffektivt. Vi kan optimalisere den ved å bruke Dynamisk programmering for å lagre minimum kutt for hver mulig papirstørrelse.
For å identifisere en hvilken som helst papirstørrelse unikt kan vi opprettholde en remSq[]-matrise slik at remSq[i] lagrer antall gjenværende firkanter med størrelse 1x1 i den ite kolonnen på papiret. Så for et papir i størrelsen 6x7 remSq[] = {6 6 6 6 6 6 6}. For å finne det nederste venstre hjørnet finner vi også den første indeksen som har maksimalt gjenværende firkanter. Så vi kan hash verdien av remSq[] array for å finne en unik nøkkel for alle mulige verdier av 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 ));
Produksjon
6
Tidskompleksitet: O(a^b) for hver av b kolonner kan vi ha a kvadrater.
Hjelpeområde: O(a^b) på grunn av memoisering som lagrer hver unike tilstand.
