Gegeven een rechthoekig papier met afmetingen een x b . De taak is om het hele papier in de minimum aantal van vierkant stukken. We kunnen vierkante stukken van elk formaat kiezen, maar ze moeten worden gesneden zonder dat ze elkaar overlappen of extra ruimte achterlaten .
Voorbeelden:
rekha indiaan
Invoer: a = 5 b = 8
5 vierkanten gesneden uit papier van formaat 5 X 8
Uitgang: 5
Uitleg: We kunnen het papier in 5 vierkanten snijden: 1 vierkant van maat 5x5 1 vierkant van maat 3x3 1 vierkant van maat 2x2 en 2 vierkanten van maat 1x1.Invoer: a = 13 b = 11
6 vierkanten gesneden uit papier van formaat 13 X 11
Uitgang: 6
Uitleg: We kunnen het papier in 6 vierkanten snijden: 1 vierkant van maat 7x7 1 vierkant van maat 6x6 1 vierkant van maat 5x5 2 vierkanten van maat 4x4 en 1 vierkant van maat 1x1.Invoer: a = 6 b = 7
5 vierkanten gesneden uit papier van formaat 6 X 7
Uitgang: 5
Uitleg: We kunnen het papier in 5 vierkanten snijden: 1 vierkant van maat 4x4, 2 vierkanten van maat 3x3 en 2 vierkanten van maat 3x3.wanneer werd de school uitgevonden?
5 vierkanten gesneden uit papier van formaat 5 X 8
6 vierkanten gesneden uit papier van formaat 13 X 11
5 vierkanten gesneden uit papier van formaat 6 X 7Inhoudsopgave
- [Onjuiste aanpak 1] Gebruik van hebzuchtige techniek
- [Onjuiste aanpak 2] Dynamisch programmeren gebruiken
- [Juiste aanpak] DFS en dynamisch programmeren gebruiken
[Onjuiste aanpak 1] Gebruik van hebzuchtige techniek
Op het eerste gezicht lijkt het misschien dat het probleem eenvoudig kan worden opgelost door eerst het grootst mogelijke vierkant uit het papier te snijden, gevolgd door het grootste vierkant uit het resterende papier te snijden, enzovoort, totdat we het hele papier hebben afgesneden. Maar deze oplossing is onjuist.
Waarom zal Greedy Approach niet werken?
Overweeg een papier van formaat 6x7 als we dan gretig proberen het papier te snijden, zullen we het krijgen 7 vierkanten: 1 vierkant van formaat 6x6 en 6 vierkantjes van formaat 1x1 terwijl de juiste oplossing is: 5. Een hebzuchtige aanpak zal dus niet werken.
sql ddl-opdrachten
[Onjuiste aanpak 2] Dynamisch programmeren gebruiken
Dynamische programmering met verticale of horizontale sneden: Een andere oplossing die misschien juist lijkt, is gebruiken Dynamische programmering . We kunnen een dp[][]-tabel zo onderhouden dp[i][j] = minimaal aantal vierkanten dat uit papier van formaat kan worden gesneden ik x j . Dan voor papier van formaat bijl
- We kunnen proberen het langs elke rij te knippen: dp[i][j] = min(dp[i][j] 1 + dp[i - k][j] + dp[k][j]) waarbij k in het bereik [1 i - 1] kan liggen.
- We kunnen proberen het langs elke kolom te knippen: dp[i][j] = min(dp[i][j] 1 + dp[i][j - k] + dp[i][k]) waarbij k in het bereik [1 j - 1] kan liggen.
Uiteindelijk zal een minimum van alle bezuinigingen het antwoord zijn. Maar ook deze oplossing is onjuist.
Waarom zal verticaal of horizontaal snijden met Dynamic Programming Approach niet werken?
arraylist.sortDit zal niet werken omdat we ervan uitgaan dat een verticale of horizontale snede de rechthoek altijd in twee delen zal verdelen. Overweeg een papier van formaat 13x11 als we vervolgens proberen het papier te knippen met behulp van de DP-aanpak, krijgen we 8 vierkanten, maar het juiste antwoord (zoals weergegeven in de voorbeelden) is 6. Daarom zal dynamisch programmeren niet werken.
[Juiste aanpak] DFS en dynamisch programmeren gebruiken
C++De idee is om het hele papier te snijden met behulp van DFS in van onderop wijze. Zoek bij elke stap de linkerbenedenhoek van het papier en probeer vanuit die hoek vierkanten van alle mogelijke afmetingen te knippen. Nadat je een vierkant hebt uitgesneden, zoek je opnieuw de linkerbenedenhoek van het resterende papier om vierkanten van alle mogelijke maten uit te snijden, enzovoort. Maar als we alle mogelijke sneden vanuit de linkerbenedenhoek van elk mogelijk papierformaat zouden proberen, zou dat behoorlijk inefficiënt zijn. We kunnen het optimaliseren door gebruik te maken van Dynamische programmering om minimale sneden voor elk mogelijk papierformaat op te slaan.
Om elk papierformaat op unieke wijze te identificeren, kunnen we een remSq[]-array bijhouden, zodat remSq[i] het aantal resterende vierkanten van formaat 1x1 in de i-de kolom van het papier opslaat. Dus voor een papierformaat van 6x7 remSq[] = {6 6 6 6 6 6 6}. Om ook de linkerbenedenhoek te vinden, zullen we de eerste index vinden met het maximale aantal resterende vierkanten. We kunnen dus de waarde van remSq[] array hashen om een unieke sleutel te vinden voor alle mogelijke waarden van remSq[] array.
// 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));
Uitvoer
6
Tijdcomplexiteit: O(a^b) voor elk van de b-kolommen kunnen we een vierkant hebben.
Hulpruimte: O(a^b) doordat memorisatie elke unieke staat opslaat.