Papir izrezan na minimalni broj kvadrata
Zadan je pravokutni papir dimenzija a x b . Zadatak je izrezati cijeli papir na minimum broj od kvadrat komada. Možemo odabrati kvadratne komade bilo koje veličine, ali oni moraju biti izrezani bez preklapanja ili ostavljanja dodatnog prostora .
Primjeri:
Ulazni: a = 5 b = 8
5 kvadrata izrezanih od papira veličine 5 X 8
Izlaz: 5
Obrazloženje: Papir možemo izrezati na 5 kvadrata: 1 kvadrat veličine 5x5 1 kvadrat veličine 3x3 1 kvadrat veličine 2x2 i 2 kvadrata veličine 1x1.Ulazni: a = 13 b = 11
6 kvadrata izrezanih od papira veličine 13 X 11
Izlaz: 6
Obrazloženje: Papir možemo izrezati na 6 kvadrata: 1 kvadrat veličine 7x7 1 kvadrat veličine 6x6 1 kvadrat veličine 5x5 2 kvadrata veličine 4x4 i 1 kvadrat veličine 1x1.Ulazni: a = 6 b = 7
5 kvadrata izrezanih od papira veličine 6 X 7
Izlaz: 5
Obrazloženje: Papir možemo izrezati na 5 kvadrata: 1 kvadrat veličine 4x4, 2 kvadrata veličine 3x3 i 2 kvadrata veličine 3x3.
5 kvadrata izrezanih od papira veličine 5 X 8 
6 kvadrata izrezanih od papira veličine 13 X 11 
5 kvadrata izrezanih od papira veličine 6 X 7 Sadržaj
- [Neispravan pristup 1] Korištenje pohlepne tehnike
- [Neispravan pristup 2] Korištenje dinamičkog programiranja
- [Ispravan pristup] Korištenje DFS-a i dinamičkog programiranja
[Neispravan pristup 1] Korištenje pohlepne tehnike
Na prvi pogled može se činiti da se problem može jednostavno riješiti tako da se prvo izreže što veći kvadrat od papira, a potom najveći kvadrat od preostalog papira i tako dok ne izrežemo cijeli papir. Ali ovo rješenje je netočno.
Zašto Greedy Approach ne funkcionira?
Razmotrite papir veličine 6x7 onda ako pokušamo pohlepno rezati papir dobit ćemo 7 kvadrati: 1 kvadrat veličine 6x6 i 6 kvadrata vel 1x1 dok je ispravno rješenje: 5. Stoga pohlepni pristup neće funkcionirati.
[Neispravan pristup 2] Korištenje dinamičkog programiranja
Dinamičko programiranje s okomitim ili vodoravnim rezovima: Drugo rješenje koje bi se moglo činiti ispravnim je korištenje Dinamičko programiranje . Možemo održavati dp[][] tablicu tako da dp[i][j] = najmanji broj kvadrata koji se mogu izrezati od papira veličine i x j . Zatim za papir vel axb
- Možemo ga pokušati rezati duž svakog reda: dp[i][j] = min(dp[i][j] 1 + dp[i - k][j] + dp[k][j]) gdje k može biti u rasponu [1 i - 1].
- Možemo ga pokušati izrezati duž svakog stupca: dp[i][j] = min(dp[i][j] 1 + dp[i][j - k] + dp[i][k]) gdje k može biti u rasponu [1 j - 1].
Na kraju će minimalni rezovi biti odgovor. Ali i ovo je rješenje netočno.
Zašto okomito ili vodoravno rezanje s pristupom dinamičkog programiranja neće funkcionirati?
Ovo neće raditi jer pretpostavljamo da će okomiti ili vodoravni rez uvijek podijeliti pravokutnik na dva dijela. Razmotrite papir veličine 13x11 onda ako pokušamo izrezati papir koristeći DP pristup, dobit ćemo 8 kvadrata, ali točan odgovor (kao što je prikazano u primjerima) je 6. Stoga dinamičko programiranje neće raditi.
[Ispravan pristup] Korištenje DFS-a i dinamičkog programiranja
C++The ideja je izrezati cijeli papir pomoću DFS u odozdo prema gore način. U svakom koraku pronađite najniži lijevi kut papira i pokušajte iz tog kuta izrezati kvadrate svih mogućih veličina. Nakon ponovnog rezanja kvadrata pronađite najniži lijevi kut preostalog papira kako biste izrezali kvadrate svih mogućih veličina i tako dalje. Ali ako pokušamo sve moguće rezove iz najnižeg lijevog kuta svake moguće veličine papira, tada bi to bilo prilično neučinkovito. Možemo ga optimizirati korištenjem Dinamičko programiranje za pohranu minimalnih rezova za svaku moguću veličinu papira.
Za jedinstvenu identifikaciju bilo koje veličine papira možemo održavati niz remSq[] tako da remSq[i] pohranjuje broj preostalih kvadrata veličine 1x1 u i-tom stupcu papira. Dakle, za papir veličine 6x7 remSq[] = {6 6 6 6 6 6 6}. Također da bismo pronašli najniži lijevi kut, naći ćemo prvi indeks koji ima najviše preostalih kvadrata. Dakle, možemo raspršiti vrijednost niza remSq[] kako bismo pronašli jedinstveni ključ za sve moguće vrijednosti niza remSq[].
// 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 ));
Izlaz
6
Vremenska složenost: O(a^b) za svaki od b stupaca možemo imati kvadrate.
Pomoćni prostor: O(a^b) zbog memoizacije pohranjujući svako jedinstveno stanje.
