נייר חתוך למספר מינימלי של ריבועים
נתון נייר מלבני של מידות a x ב . המשימה היא לחתוך את כל הנייר לתוך מִינִימוּם מספר של מְרוּבָּע חתיכות. אנו יכולים לבחור חתיכות מרובעות בכל גודל אך יש לחתוך אותן מבלי לחפוף או להשאיר מקום נוסף .
דוגמאות:
קֶלֶט: a = 5 b = 8
5 ריבועים חתוכים מנייר בגודל 5 X 8
תְפוּקָה: 5
הֶסבֵּר: נוכל לחתוך את הנייר ל-5 ריבועים: 1 ריבוע בגודל 5x5 1 ריבוע בגודל 3x3 1 ריבוע בגודל 2x2 ו-2 ריבועים בגודל 1x1.קֶלֶט: a = 13 b = 11
6 ריבועים חתוכים מנייר בגודל 13 X 11
תְפוּקָה: 6
הֶסבֵּר: אנחנו יכולים לחתוך את הנייר ל-6 ריבועים: ריבוע אחד בגודל 7x7 1 ריבוע בגודל 6x6 1 ריבוע בגודל 5x5 2 ריבועים בגודל 4x4 וריבוע אחד בגודל 1x1.קֶלֶט: a = 6 b = 7
5 ריבועים חתוכים מנייר בגודל 6 X 7
תְפוּקָה: 5
הֶסבֵּר: נוכל לחתוך את הנייר ל-5 ריבועים: ריבוע אחד בגודל 4x4 2 ריבועים בגודל 3x3 ו-2 ריבועים בגודל 3x3.
5 ריבועים חתוכים מנייר בגודל 5 X 8 
6 ריבועים חתוכים מנייר בגודל 13 X 11 
5 ריבועים חתוכים מנייר בגודל 6 X 7 תוכן עניינים
- [גישה שגויה 1] שימוש בטכניקה חמדנית
- [גישה שגויה 2] שימוש בתכנות דינמי
- [גישה נכונה] שימוש ב-DFS ובתכנות דינמי
[גישה שגויה 1] שימוש בטכניקה חמדנית
במבט ראשון אולי נראה שניתן לפתור את הבעיה בקלות על ידי חיתוך הריבוע הגדול ביותר האפשרי מהנייר תחילה ולאחר מכן חיתוך הריבוע הגדול ביותר מהנייר שנותר וכן הלאה עד שגזור את כל הנייר. אבל הפתרון הזה לא נכון.
למה הגישה החמדנית לא תעבוד?
שקול נייר בגודל 6x7 אז אם ננסה לחתוך את הנייר בתאווה, נקבל 7 ריבועים: 1 ריבוע בגודל 6x6 ו-6 ריבועים בגודל 1x1 ואילו הפתרון הנכון הוא: 5. מכאן שהגישה החמדנית לא תעבוד.
[גישה שגויה 2] שימוש בתכנות דינמי
תכנות דינמי עם חיתוכים אנכיים או אופקיים: פתרון נוסף שעשוי להיראות נכון הוא שימוש תכנות דינמי . אנחנו יכולים לשמור על טבלת dp[][] כך dp[i][j] = מספר מינימלי של ריבועים שניתן לגזור מנייר בגודל i x j . ואז לנייר בגודל axb
- אנחנו יכולים לנסות לחתוך אותו לאורך כל שורה: dp[i][j] = min(dp[i][j] 1 + dp[i - k][j] + dp[k][j]) כאשר k יכול להיות בטווח [1 i - 1].
- נוכל לנסות לחתוך אותו לאורך כל עמודה: dp[i][j] = min(dp[i][j] 1 + dp[i][j - k] + dp[i][k]) כאשר k יכול להיות בטווח [1 j - 1].
לבסוף מינימום מכל הקיצוצים תהיה התשובה. אבל גם הפתרון הזה לא נכון.
מדוע חיתוך אנכי או אופקי עם גישת תכנות דינמית לא יעבוד?
זה לא יעבוד כי אנחנו מניחים שחתוך אנכי או אופקי תמיד יחלק את המלבן לשני חלקים. שקול נייר בגודל 13x11 אז אם ננסה לחתוך את הנייר באמצעות גישת DP נקבל 8 ריבועים אבל התשובה הנכונה (כפי שמוצג בדוגמאות) היא 6. לפיכך תכנות דינמי לא יעבוד.
[גישה נכונה] שימוש ב-DFS ובתכנות דינמי
C++ה רַעְיוֹן הוא לחתוך את כל הנייר באמצעות DFS ב מלמטה למעלה דֶרֶך. בכל שלב מצא את הפינה השמאלית התחתונה ביותר של הנייר ונסו לגזור ריבועים בכל גודל אפשרי מאותה פינה. לאחר חיתוך ריבוע שוב מצא את הפינה השמאלית התחתונה ביותר של הנייר שנותר כדי לחתוך ריבועים בכל הגדלים האפשריים וכן הלאה. אבל אם ננסה את כל החיתוכים האפשריים מהפינה השמאלית התחתונה של כל גודל נייר אפשרי אז זה יהיה די לא יעיל. אנחנו יכולים לייעל אותו באמצעות תכנות דינמי לאחסן מינימום חתכים עבור כל גודל נייר אפשרי.
כדי לזהות באופן ייחודי כל גודל נייר נוכל לשמור על מערך remSq[] כך ש-remSq[i] מאחסן את מספר הריבועים שנותרו בגודל 1x1 בעמודה ה-איטית של הנייר. אז עבור נייר בגודל 6x7 remSq[] = {6 6 6 6 6 6 6}. כמו כן, כדי למצוא את הפינה השמאלית התחתונה ביותר, נמצא את האינדקס הראשון עם הריבועים המרביים שנותרו. אז נוכל לגיבוב את הערך של מערך remSq[] כדי למצוא מפתח ייחודי לכל הערכים האפשריים של מערך 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 ));
תְפוּקָה
6
מורכבות זמן: O(a^b) עבור כל אחת מעמודות b אנחנו יכולים לקבל ריבועים.
מרחב עזר: O(a^b) עקב זיכרון האחסון של כל מצב ייחודי.
