Papier pocięty na minimalną liczbę kwadratów
Biorąc pod uwagę prostokątny papier o wymiarach a x b . Zadanie polega na wycięciu całego papieru w tzw minimum liczba kwadrat sztuki. Możemy wybrać kawałki kwadratów o dowolnej wielkości, ale należy je wyciąć bez nakładania się i pozostawiania dodatkowej przestrzeni .
Przykłady:
Wejście: a = 5 b = 8
5 kwadratów wyciętych z papieru o rozmiarze 5 X 8
Wyjście: 5
Wyjaśnienie: Papier możemy pociąć na 5 kwadratów: 1 kwadrat o wymiarach 5x5 1 kwadrat o wymiarach 3x3 1 kwadrat o wymiarach 2x2 i 2 kwadraty o wymiarach 1x1.Wejście: a = 13 b = 11
6 kwadratów wyciętych z papieru o rozmiarze 13 X 11
Wyjście: 6
Wyjaśnienie: Papier możemy pociąć na 6 kwadratów: 1 kwadrat o wymiarach 7x7 1 kwadrat o wymiarach 6x6 1 kwadrat o wymiarach 5x5 2 kwadraty o wymiarach 4x4 i 1 kwadrat o wymiarach 1x1.Wejście: a = 6 b = 7
5 kwadratów wyciętych z papieru o rozmiarze 6 X 7
Wyjście: 5
Wyjaśnienie: Papier możemy pociąć na 5 kwadratów: 1 kwadrat o wymiarach 4x4, 2 kwadraty o wymiarach 3x3 i 2 kwadraty o wymiarach 3x3.
5 kwadratów wyciętych z papieru o rozmiarze 5 X 8 
6 kwadratów wyciętych z papieru o rozmiarze 13 X 11 
5 kwadratów wyciętych z papieru o rozmiarze 6 X 7 Spis treści
- [Nieprawidłowe podejście 1] Używanie zachłannej techniki
- [Nieprawidłowe podejście 2] Korzystanie z programowania dynamicznego
- [Właściwe podejście] Korzystanie z DFS i programowania dynamicznego
[Nieprawidłowe podejście 1] Używanie zachłannej techniki
Na pierwszy rzut oka mogłoby się wydawać, że problem można łatwo rozwiązać wycinając najpierw z papieru jak największy kwadrat, a następnie z reszty papieru wycinając największy kwadrat i tak dalej, aż wytniemy cały papier. Ale to rozwiązanie jest nieprawidłowe.
Dlaczego podejście zachłanne nie zadziała?
Rozważ papier o odpowiednim rozmiarze 6x7 wtedy, jeśli spróbujemy łapczywie przeciąć papier, otrzymamy 7 kwadraty: 1 kwadratowy rozmiar 6x6 i 6 kwadratów wielkości 1x1 podczas gdy prawidłowe rozwiązanie to: 5. Dlatego zachłanne podejście nie zadziała.
[Nieprawidłowe podejście 2] Korzystanie z programowania dynamicznego
Programowanie dynamiczne z nacięciami pionowymi lub poziomymi: Innym rozwiązaniem, które może wydawać się poprawne, jest użycie Programowanie dynamiczne . Możemy utrzymać tabelę dp[][] w taki sposób dp[i]j] = minimalna liczba kwadratów, które można wyciąć z papieru o rozmiarze ja x j . Następnie dla papieru o rozmiarze axb
- Możemy spróbować przeciąć go wzdłuż każdego rzędu: dp[i][j] = min(dp[i][j] 1 + dp[i - k][j] + dp[k][j]) gdzie k może należeć do zakresu [1 i - 1].
- Możemy spróbować przeciąć go wzdłuż każdej kolumny: dp[i][j] = min(dp[i][j] 1 + dp[i][j - k] + dp[i][k]) gdzie k może należeć do zakresu [1 j - 1].
Wreszcie odpowiedzią będzie minimum wszystkich cięć. Ale to rozwiązanie jest również nieprawidłowe.
Dlaczego cięcie w pionie lub w poziomie przy użyciu podejścia programowania dynamicznego nie zadziała?
To nie zadziała, ponieważ zakładamy, że cięcie pionowe lub poziome zawsze podzieli prostokąt na dwie części. Rozważ papier o odpowiednim rozmiarze 13x11 wtedy, jeśli spróbujemy wyciąć papier metodą DP, otrzymamy 8 kwadratów, ale poprawna odpowiedź (jak pokazano w przykładach) to 6. Dlatego programowanie dynamiczne nie będzie działać.
[Właściwe podejście] Korzystanie z DFS i programowania dynamicznego
C++The pomysł polega na przecięciu całego papieru za pomocą DFS W oddolnie sposób. W każdym kroku znajdź lewy dolny róg kartki i spróbuj wyciąć z niego kwadraty dowolnej wielkości. Po ponownym wycięciu kwadratu znajdź lewy dolny róg pozostałego papieru, aby wyciąć kwadraty wszystkich możliwych rozmiarów i tak dalej. Jeśli jednak spróbujemy wykonać wszystkie możliwe cięcia w lewym dolnym rogu każdego możliwego rozmiaru papieru, będzie to dość nieefektywne. Możemy to zoptymalizować za pomocą Programowanie dynamiczne do przechowywania minimalnych cięć dla każdego możliwego rozmiaru papieru.
Aby jednoznacznie zidentyfikować dowolny rozmiar papieru, możemy zachować tablicę remSq[] taką, że remSq[i] przechowuje liczbę pozostałych kwadratów o rozmiarze 1x1 w i-tej kolumnie papieru. Zatem dla papieru o wymiarach 6x7 remSq[] = {6 6 6 6 6 6 6}. Aby znaleźć najniższy lewy róg, znajdziemy pierwszy indeks mający maksymalną liczbę pozostałych kwadratów. Możemy więc zahaszować wartość tablicy remSq[], aby znaleźć unikalny klucz dla wszystkich możliwych wartości tablicy 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 ));
Wyjście
6
Złożoność czasowa: O(a^b) dla każdej z b kolumn możemy mieć kwadraty.
Przestrzeń pomocnicza: O(a^b) dzięki zapamiętywaniu przechowującemu każdy unikalny stan.
