Gegeben sei ein rechteckiges Papier mit Abmessungen a x b . Die Aufgabe besteht darin, das gesamte Papier in das Papier zu schneiden Minimum Anzahl von Quadrat Stücke. Wir können quadratische Stücke jeder Größe wählen, diese müssen jedoch geschnitten werden ohne sich zu überlappen oder zusätzlichen Platz zu lassen .
Beispiele:
Eingang: a = 5 b = 8
5 Quadrate aus Papier der Größe 5 x 8 ausschneiden
Ausgabe: 5
Erläuterung: Wir können das Papier in 5 Quadrate schneiden: 1 Quadrat der Größe 5x5, 1 Quadrat der Größe 3x3, 1 Quadrat der Größe 2x2 und 2 Quadrate der Größe 1x1.Eingang: a = 13 b = 11
6 Quadrate aus Papier der Größe 13 x 11 ausschneiden
Ausgabe: 6
Erläuterung: Wir können das Papier in 6 Quadrate schneiden: 1 Quadrat der Größe 7x7, 1 Quadrat der Größe 6x6, 1 Quadrat der Größe 5x5, 2 Quadrate der Größe 4x4 und 1 Quadrat der Größe 1x1.Eingang: a = 6 b = 7
5 Quadrate aus Papier der Größe 6 x 7 ausschneiden
Ausgabe: 5
Erläuterung: Wir können das Papier in 5 Quadrate schneiden: 1 Quadrat der Größe 4x4, 2 Quadrate der Größe 3x3 und 2 Quadrate der Größe 3x3.
5 Quadrate aus Papier der Größe 5 x 8 ausschneiden
6 Quadrate aus Papier der Größe 13 x 11 ausschneiden
5 Quadrate aus Papier der Größe 6 x 7 ausschneidenInhaltsverzeichnis
- [Falscher Ansatz 1] Verwendung der Greedy-Technik
- [Falscher Ansatz 2] Verwendung dynamischer Programmierung
- [Richtiger Ansatz] Verwendung von DFS und dynamischer Programmierung
[Falscher Ansatz 1] Verwendung der Greedy-Technik
Auf den ersten Blick könnte es scheinen, dass das Problem leicht gelöst werden kann, indem man zuerst das größtmögliche Quadrat aus dem Papier ausschneidet, dann das größte Quadrat aus dem restlichen Papier ausschneidet und so weiter, bis wir das gesamte Papier ausgeschnitten haben. Aber diese Lösung ist falsch.
Warum funktioniert der Greedy-Ansatz nicht?
Betrachten Sie ein Papier der Größe 6x7 Wenn wir dann gierig versuchen, das Papier zu zerschneiden, werden wir es bekommen 7 Quadrate: 1 Quadrat der Größe 6x6 und 6 Quadrate groß 1x1 wohingegen die richtige Lösung lautet: 5. Daher wird ein gieriger Ansatz nicht funktionieren.
[Falscher Ansatz 2] Verwendung dynamischer Programmierung
Dynamische Programmierung mit vertikalen oder horizontalen Schnitten: Eine andere Lösung, die richtig erscheinen könnte, ist die Verwendung Dynamische Programmierung . Wir können eine solche dp[][]-Tabelle verwalten dp[i][j] = Mindestanzahl an Quadraten, die aus Papier der Größe geschnitten werden können ich x j . Dann für Papier der Größe Axt
Karte vs. Satz
- Wir können versuchen, es entlang jeder Reihe zu schneiden: dp[i][j] = min(dp[i][j] 1 + dp[i - k][j] + dp[k][j]) wobei k im Bereich [1 i - 1] liegen kann.
- Wir können versuchen, es entlang jeder Spalte zu schneiden: dp[i][j] = min(dp[i][j] 1 + dp[i][j - k] + dp[i][k]) wobei k im Bereich [1 j - 1] liegen kann.
Letztendlich wird das Minimum aller Kürzungen die Lösung sein. Aber auch diese Lösung ist falsch.
Warum funktioniert das vertikale oder horizontale Schneiden mit dem Dynamic Programming Approach nicht?
Dies wird nicht funktionieren, da wir davon ausgehen, dass ein vertikaler oder horizontaler Schnitt das Rechteck immer in zwei Teile teilt. Betrachten Sie ein Papier der Größe 13x11 Wenn wir dann versuchen, das Papier mit dem DP-Ansatz zu schneiden, erhalten wir 8 Quadrate, aber die richtige Antwort (wie in den Beispielen gezeigt) ist 6. Daher funktioniert die dynamische Programmierung nicht.
[Richtiger Ansatz] Verwendung von DFS und dynamischer Programmierung
C++Der Idee besteht darin, das gesamte Papier mit zu schneiden DFS In von unten nach oben Benehmen. Suchen Sie bei jedem Schritt die unterste linke Ecke des Papiers und versuchen Sie, aus dieser Ecke Quadrate aller möglichen Größen auszuschneiden. Suchen Sie nach dem Ausschneiden eines Quadrats erneut die unterste linke Ecke des verbleibenden Papiers, um Quadrate in allen möglichen Größen usw. auszuschneiden. Aber wenn wir alle möglichen Schnitte von der untersten linken Ecke jedes möglichen Papierformats aus versuchen würden, wäre das ziemlich ineffizient. Wir können es optimieren, indem wir verwenden Dynamische Programmierung um Mindestschnitte für jedes mögliche Papierformat zu speichern.
Um jede Papiergröße eindeutig zu identifizieren, können wir ein remSq[]-Array verwalten, sodass remSq[i] die Anzahl der verbleibenden Quadrate der Größe 1x1 in der i-ten Spalte des Papiers speichert. Für ein Papier der Größe 6x7 gilt also remSq[] = {6 6 6 6 6 6 6}. Um auch die unterste linke Ecke zu finden, suchen wir den ersten Index mit den meisten verbleibenden Quadraten. Wir können also den Wert des Arrays remSq[] hashen, um einen eindeutigen Schlüssel für alle möglichen Werte des Arrays remSq[] zu finden.
// C++ Program to find minimum number of squares to cut // from a paper of size axb #include
// 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 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# 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 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));
Ausgabe
6
Zeitkomplexität: O(a^b) Für jede der b-Spalten können wir ein Quadrat haben.
Hilfsraum: O(a^b) aufgrund der Memoisierung, die jeden einzelnen Zustand speichert.