PAPEL CORTADO EM NÚMERO MÍNIMO DE QUADRADOS

Dado um papel retangular de dimensões a x b . A tarefa é cortar todo o papel no mínimo número de quadrado peças. Podemos escolher peças quadradas de qualquer tamanho, mas devem ser cortadas sem sobrepor ou deixar qualquer espaço extra .

Exemplos:

Entrada: uma = 5 b = 8

5 quadrados cortados de papel de tamanho 5 X 8
Saída: 5
Explicação: Podemos cortar o papel em 5 quadrados: 1 quadrado de tamanho 5x5 1 quadrado de tamanho 3x3 1 quadrado de tamanho 2x2 e 2 quadrados de tamanho 1x1.
Entrada: uma = 13 b = 11
6 quadrados cortados de papel de tamanho 13 X 11
Saída: 6
Explicação: Podemos cortar o papel em 6 quadrados: 1 quadrado de tamanho 7x7 1 quadrado de tamanho 6x6 1 quadrado de tamanho 5x5 2 quadrados de tamanho 4x4 e 1 quadrado de tamanho 1x1.
seleção de múltiplas tabelas sql
Entrada: uma = 6 b = 7
5 quadrados cortados de papel de tamanho 6 X 7
Saída: 5
Explicação: Podemos cortar o papel em 5 quadrados: 1 quadrado de tamanho 4x4 2 quadrados de tamanho 3x3 e 2 quadrados de tamanho 3x3.

Índice

[Abordagem incorreta 1] Usando técnica gananciosa
[Abordagem incorreta 2] Usando programação dinâmica
[Abordagem Correta] Usando DFS e Programação Dinâmica

[Abordagem incorreta 1] Usando técnica gananciosa

À primeira vista, pode parecer que o problema pode ser facilmente resolvido cortando primeiro o maior quadrado possível do papel, seguido do corte do maior quadrado do papel restante e assim por diante, até cortarmos todo o papel. Mas esta solução está incorreta.
Por que a abordagem gananciosa não funciona?
Considere um papel de tamanho 6x7 então, se tentarmos cortar o papel com avidez, obteremos 7 quadrados: 1 quadrado de tamanho 6x6 e 6 quadrados de tamanho 1x1 enquanto a solução correta é: 5. Portanto, uma abordagem gananciosa não funcionará.

[Abordagem incorreta 2] Usando programação dinâmica

Programação Dinâmica com cortes verticais ou horizontais: Outra solução que pode parecer correta é usar Programação Dinâmica . Podemos manter uma tabela dp[][] tal que dp[i][j] = número mínimo de quadrados que podem ser cortados de papel de tamanho eu x j . Então para papel de tamanho axb
Podemos tentar cortá-lo ao longo de cada linha: dp[i][j] = min(dp[i][j] 1 + dp[i - k][j] + dp[k][j]) onde k pode estar no intervalo [1 i - 1].
Podemos tentar cortá-lo ao longo de cada coluna: dp[i][j] = min(dp[i][j] 1 + dp[i][j - k] + dp[i][k]) onde k pode estar no intervalo [1 j - 1].
Finalmente, o mínimo de todos os cortes será a resposta. Mas esta solução também está incorreta.
se mais se mais se java
Por que cortar vertical ou horizontalmente com a Abordagem de Programação Dinâmica não funciona?
Isso não funcionará porque estamos assumindo que um corte vertical ou horizontal sempre dividirá o retângulo em duas partes. Considere um papel de tamanho 13x11 então, se tentarmos cortar o papel usando a abordagem DP, obteremos 8 quadrados, mas a resposta correta (como mostrado nos exemplos) é 6. Conseqüentemente, a Programação Dinâmica não funcionará.

[Abordagem Correta] Usando DFS e Programação Dinâmica

O ideia é cortar todo o papel usando DFS em baixo para cima maneiras. Em cada etapa, encontre o canto inferior esquerdo do papel e tente cortar quadrados de todos os tamanhos possíveis desse canto. Depois de cortar um quadrado novamente, encontre o canto esquerdo inferior do papel restante para cortar quadrados de todos os tamanhos possíveis e assim por diante. Mas se tentarmos todos os cortes possíveis a partir do canto inferior esquerdo de todos os tamanhos de papel possíveis, isso será bastante ineficiente. Podemos otimizá-lo usando Programação Dinâmica para armazenar cortes mínimos para cada tamanho de papel possível.
Para identificar exclusivamente qualquer tamanho de papel, podemos manter um array remSq[] tal que remSq[i] armazene o número de quadrados restantes de tamanho 1x1 na i-ésima coluna do papel. Portanto, para um papel de tamanho 6x7 remSq[] = {6 6 6 6 6 6 6}. Além disso, para encontrar o canto inferior esquerdo, encontraremos o primeiro índice com o máximo de quadrados restantes. Portanto, podemos fazer o hash do valor do array remSq[] para encontrar uma chave exclusiva para todos os valores possíveis do array remSq[].

C++

// 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# 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));

Saída

Complexidade de tempo: O (a ^ b) para cada uma das b colunas podemos ter a quadrados.
Espaço Auxiliar: O(a^b) devido à memoização que armazena cada estado único.

TechCodeview

Papel cortado em número mínimo de quadrados

[Abordagem incorreta 1] Usando técnica gananciosa

[Abordagem incorreta 2] Usando programação dinâmica

[Abordagem Correta] Usando DFS e Programação Dinâmica