Papper klippt i minsta antal rutor
Givet ett rektangulärt papper av dimensioner a x b . Uppgiften är att skära hela papperet i minimum antal fyrkant bitar. Vi kan välja fyrkantiga bitar av alla storlekar men de måste skäras utan att överlappa eller lämna något extra utrymme .
Exempel:
Input: a = 5 b = 8
5 rutor skurna från papper i storlek 5 X 8
Produktion: 5
Förklaring: Vi kan skära papperet i 5 rutor: 1 kvadrat med storleken 5x5 1 kvadrat med storleken 3x3 1 kvadrat med storleken 2x2 och 2 rutor av storleken 1x1.Input: a = 13 b = 11
6 rutor skurna från papper i storleken 13 X 11
Produktion: 6
Förklaring: Vi kan skära papperet i 6 rutor: 1 kvadrat med storleken 7x7 1 kvadrat med storleken 6x6 1 kvadrat med storleken 5x5 2 rutor i storleken 4x4 och 1 kvadrat med storleken 1x1.Input: a = 6 b = 7
5 rutor skurna från papper i storlek 6 X 7
Produktion: 5
Förklaring: Vi kan skära papperet i 5 rutor: 1 rutor i storleken 4x4 2 rutor i storleken 3x3 och 2 rutor i storleken 3x3.
5 rutor skurna från papper i storlek 5 X 8 
6 rutor skurna från papper i storleken 13 X 11 
5 rutor skurna från papper i storlek 6 X 7 Innehållsförteckning
- [Felaktig metod 1] Använder girig teknik
- [Felaktig metod 2] Använder dynamisk programmering
- [Korrekt tillvägagångssätt] Använda DFS och dynamisk programmering
[Felaktig metod 1] Använder girig teknik
Vid första anblicken kan det tyckas som om problemet lätt kan lösas genom att först skära den största kvadraten från pappret, följt av att skära den största kvadraten från det återstående papperet och så vidare tills vi har klippt hela papperet. Men denna lösning är felaktig.
Varför Greedy Approach fungerar inte?
Tänk på ett papper av storlek 6x7 sedan om vi försöker klippa papperet girigt kommer vi att få 7 rutor: 1 kvadrat av storlek 6x6 och 6 kvadrater i storlek 1x1 Den korrekta lösningen är: 5. Därför fungerar inte girig strategi.
[Felaktig metod 2] Använder dynamisk programmering
Dynamisk programmering med vertikala eller horisontella snitt: En annan lösning som kan verka korrekt är att använda Dynamisk programmering . Vi kan upprätthålla en dp[][]-tabell så att dp[i][j] = minsta antal rutor som kan skäras från papper av storlek i x j . Sedan för papper av storlek axb
- Vi kan försöka skära den längs varje rad: dp[i][j] = min(dp[i][j] 1 + dp[i - k][j] + dp[k][j]) där k kan vara i området [1 i - 1].
- Vi kan försöka klippa det längs varje kolumn: dp[i][j] = min(dp[i][j] 1 + dp[i][j - k] + dp[i][k]) där k kan vara i området [1 j - 1].
Slutligen kommer ett minimum av alla nedskärningar att vara svaret. Men denna lösning är också felaktig.
Varför fungerar det inte att skära vertikalt eller horisontellt med Dynamic Programming Approach?
Detta kommer inte att fungera eftersom vi antar att ett vertikalt eller horisontellt snitt alltid kommer att dela rektangeln i två delar. Tänk på ett papper av storlek 13x11 Om vi sedan försöker klippa papperet med DP-metoden får vi 8 rutor men det korrekta svaret (som visas i exemplen) är 6. Därför fungerar inte dynamisk programmering.
[Korrekt tillvägagångssätt] Använda DFS och dynamisk programmering
C++De aning är att skära hela papperet med hjälp av DFS i nedifrån och upp sätt. I varje steg leta reda på det nedre vänstra hörnet av papperet och försök skära ut rutor av alla möjliga storlekar från det hörnet. Efter att ha klippt en fyrkant igen, leta reda på det nedre vänstra hörnet av det återstående papperet för att skära ut rutor av alla möjliga storlekar och så vidare. Men om vi försöker alla möjliga klipp från det lägsta vänstra hörnet av alla möjliga pappersstorlekar så skulle det vara ganska ineffektivt. Vi kan optimera det genom att använda Dynamisk programmering för att lagra minsta möjliga snitt för varje möjlig pappersstorlek.
För att unikt identifiera vilken pappersstorlek som helst kan vi upprätthålla en remSq[]-array så att remSq[i] lagrar antalet återstående kvadrater med storleken 1x1 i den i:te kolumnen på papperet. Så för ett papper med storleken 6x7 remSq[] = {6 6 6 6 6 6 6}. Också för att hitta det lägsta vänstra hörnet hittar vi det första indexet som har maximalt kvarvarande kvadrater. Så vi kan hasha värdet på remSq[]-arrayen för att hitta en unik nyckel för alla möjliga värden för remSq[]-arrayen.
// 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
Tidskomplexitet: O(a^b) för var och en av b kolumner kan vi ha en kvadrat.
Hjälputrymme: O(a^b) på grund av memoisering som lagrar varje unikt tillstånd.
