Dado un papel de tamaño A x B. La tarea es cortar el papel en cuadrados de cualquier tamaño. Encuentra el número mínimo de cuadrados que se pueden cortar del papel.
Ejemplos:
Input : 36 x 30 Output : 5 Explanation : 3 (squares of size 12x12) + 2 (squares of size 18x18) Input : 4 x 5 Output : 5 Explanation : 1 (squares of size 4x4) + 4 (squares of size 1x1)
Preguntado en: Google
Ya hemos discutido el enfoque Greedy para resolver este problema en el artículo anterior . Pero el enfoque anterior no siempre funciona. Por ejemplo, falla en el primer caso de prueba anterior. Entonces, en este artículo resolvemos este problema usando Programación Dinámica .
Sabemos que si queremos cortar el número mínimo de cuadrados del papel, primero tendríamos que cortar el cuadrado más grande posible del papel y el cuadrado más grande tendrá el mismo lado que el lado más pequeño del papel. Por ejemplo, si el papel tiene un tamaño de 13 x 29, entonces el cuadrado máximo será de lado 13, por lo que podemos cortar 2 cuadrados de tamaño 13 x 13 (29/13 = 2). Ahora, el papel restante tendrá un tamaño de 3 x 13. Del mismo modo, podemos cortar el papel restante utilizando 4 cuadrados de tamaño 3 x 3 y 3 cuadrados de 1 x 1. Por lo tanto, se pueden cortar un mínimo de 9 cuadrados del papel de tamaño 13 x 29.
Explicación :
mínimoCuadrado es una función que intenta dividir el rectángulo en alguna posición. La función se llama recursivamente para ambas partes. Pruebe todas las divisiones posibles y elija la que tenga el mínimo resultado. El caso base es cuando ambos lados son iguales, es decir, la entrada ya es un cuadrado, en cuyo caso el resultado es Estamos tratando de encontrar el corte más cercano al centro que nos llevará a nuestro resultado mínimo.
Suponiendo que tenemos un rectángulo con un ancho N y una altura M.
- si (N == M), entonces es un cuadrado y no hay que hacer nada.
- De lo contrario, podemos dividir el rectángulo en otros dos más pequeños (N – x, M) y (x, M), por lo que se puede resolver recursivamente.
- Del mismo modo, también podemos dividirlo en (N, M – x) y (N, x)
También debemos tener en cuenta un caso límite aquí que es N = 11 y M = 13 o viceversa. La siguiente será la mejor respuesta posible para el caso de prueba dado:
Nuestro enfoque devolverá 8 para este caso, pero como puede ver, podemos cortar el papel en 6 cuadrados, que es un mínimo. Esto sucede porque no hay una línea vertical u horizontal que atraviese todo el cuadrado en la solución óptima.
A continuación se muestra la implementación de la idea anterior utilizando Programación Dinámica.
C++
// C++ program to find minimum number of squares
// to cut a paper using Dynamic Programming
#include<bits/stdc++.h>
using namespace std;
const int MAX = 300;
int dp[MAX][MAX];
// Returns min number of squares needed
int minimumSquare(int m, int n)
{
// Initializing max values to vertical_min
// and horizontal_min
int vertical_min = INT_MAX;
int horizontal_min = INT_MAX;
// N=11 & M=13 is a special case
if(n==13 && m==11) return 6;
if(m==13 && n==11) return 6;
// If the given rectangle is already a square
if (m == n)
return 1;
// If the answer for the given rectangle is
// previously calculated return that answer
if (dp[m][n])
return dp[m][n];
/* The rectangle is cut horizontally and
vertically into two parts and the cut
with minimum value is found for every
recursive call.
*/
for (int i = 1;i<= m/2;i++)
{
// Calculating the minimum answer for the
// rectangles with width equal to n and length
// less than m for finding the cut point for
// the minimum answer
horizontal_min = min(minimumSquare(i, n) +
minimumSquare(m-i, n), horizontal_min);
}
for (int j = 1;j<= n/2;j++)
{
// Calculating the minimum answer for the
// rectangles with width less than n and
// length equal to m for finding the cut
// point for the minimum answer
vertical_min = min(minimumSquare(m, j) +
minimumSquare(m, n-j), vertical_min);
}
// Minimum of the vertical cut or horizontal
// cut to form a square is the answer
dp[m][n] = min(vertical_min, horizontal_min);
return dp[m][n];
}
// Driver code
int main()
{
int m = 30, n = 35;
// Function call
cout << minimumSquare(m, n);
return 0;
}
// This code is contributed by Utkarsh Gupta
Java
// Java program to find minimum number of
// squares to cut a paper using Dynamic
// Programming
import java.io.*;
class GFG {
static int dp[][] = new int[300][300];
// Returns min number of squares needed
static int minimumSquare(int m, int n)
{
// Initializing max values to
// vertical_min and horizontal_min
int vertical_min = Integer.MAX_VALUE;
int horizontal_min = Integer.MAX_VALUE;
// N=11 & M=13 is a special case
if(n==13 && m==11) return 6;
if(m==13 && n==11) return 6;
// If the given rectangle is
// already a square
if (m == n)
return 1;
// If the answer for the given
// rectangle is previously
// calculated return that answer
if (dp[m][n] != 0)
return dp[m][n];
/* The rectangle is cut horizontally
and vertically into two parts and
the cut with minimum value is found
for every recursive call.
*/
for (int i = 1; i <= m / 2; i++)
{
// Calculating the minimum answer
// for the rectangles with width
// equal to n and length less than
// m for finding the cut point for
// the minimum answer
horizontal_min
= Math.min(minimumSquare(i, n)
+ minimumSquare(m - i, n),
horizontal_min);
}
for (int j = 1; j <= n / 2; j++) {
// Calculating the minimum answer
// for the rectangles with width
// less than n and length equal to
// m for finding the cut point for
// the minimum answer
vertical_min
= Math.min(minimumSquare(m, j)
+ minimumSquare(m, n - j),
vertical_min);
}
// Minimum of the vertical cut or
// horizontal cut to form a square
// is the answer
dp[m][n] = Math.min(vertical_min, horizontal_min);
return dp[m][n];
}
// Driver code
public static void main(String[] args)
{
int m = 30, n = 35;
// Function call
System.out.println(minimumSquare(m, n));
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 program to find minimum # number of squares # to cut a paper using Dynamic Programming MAX = 300 dp = [[0 for i in range(MAX)] for i in range(MAX)] # Returns min number of squares needed def minimumSquare(m, n): # Initializing max values to # vertical_min # and horizontal_min vertical_min = 10000000000 horizontal_min = 10000000000 # N=11 & M=13 is a special case if n == 13 and m == 11: return 6 if m == 13 and n == 11: return 6 # If the given rectangle is # already a square if m == n: return 1 # If the answer for the given rectangle is # previously calculated return that answer if dp[m][n] != 0: return dp[m][n] # The rectangle is cut horizontally and # vertically into two parts and the cut # with minimum value is found for every # recursive call. for i in range(1, m//2+1): # Calculating the minimum answer for the # rectangles with width equal to n and length # less than m for finding the cut point for # the minimum answer horizontal_min = min(minimumSquare(i, n) + minimumSquare(m-i, n), horizontal_min) for j in range(1, n//2+1): # Calculating the minimum answer for the # rectangles with width equal to n and length # less than m for finding the cut point for # the minimum answer vertical_min = min(minimumSquare(m, j) + minimumSquare(m, n-j), vertical_min) # Minimum of the vertical cut or horizontal # cut to form a square is the answer dp[m][n] = min(vertical_min, horizontal_min) return dp[m][n] # Driver code if __name__ == '__main__': m = 30 n = 35 # Function call print(minimumSquare(m, n)) # This code is contributed by sahilshelangia
C#
// C# program to find minimum number of
// squares to cut a paper using Dynamic
// Programming
using System;
class GFG {
static int[, ] dp = new int[300, 300];
// Returns min number of squares needed
static int minimumSquare(int m, int n)
{
// Initializing max values to
// vertical_min and horizontal_min
int vertical_min = int.MaxValue;
int horizontal_min = int.MaxValue;
// N=11 & M=13 is a special case
if(n==13 && m==11) return 6;
if(m==13 && n==11) return 6;
// If the given rectangle is
// already a square
if (m == n)
return 1;
// If the answer for the given
// rectangle is previously
// calculated return that answer
if (dp[m, n] != 0)
return dp[m, n];
/* The rectangle is cut horizontally
and vertically into two parts and
the cut with minimum value is found
for every recursive call.
*/
for (int i = 1; i <= m / 2; i++)
{
// Calculating the minimum answer
// for the rectangles with width
// equal to n and length less than
// m for finding the cut point for
// the minimum answer
horizontal_min
= Math.Min(minimumSquare(i, n)
+ minimumSquare(m - i, n),
horizontal_min);
}
for (int j = 1; j <= n / 2; j++)
{
// Calculating the minimum answer
// for the rectangles with width
// less than n and length equal to
// m for finding the cut point for
// the minimum answer
vertical_min
= Math.Min(minimumSquare(m, j)
+ minimumSquare(m, n - j),
vertical_min);
}
// Minimum of the vertical cut or
// horizontal cut to form a square
// is the answer
dp[m, n] = Math.Min(vertical_min, horizontal_min);
return dp[m, n];
}
// Driver code
public static void Main()
{
int m = 30, n = 35;
// Function call
Console.WriteLine(minimumSquare(m, n));
}
}
// This code is contributed by anuj_67.
Javascript
<script>
// Javascript program to find minimum number of
// squares to cut a paper using Dynamic
// Programming
let dp = new Array(300);
for(let i = 0; i < 300; i++)
{
dp[i] = new Array(300);
for(let j = 0; j < 300; j++)
{
dp[i][j] = 0;
}
}
// Returns min number of squares needed
function minimumSquare(m, n)
{
// Initializing max values to
// vertical_min and horizontal_min
let vertical_min = Number.MAX_VALUE;
let horizontal_min = Number.MAX_VALUE;
// N=11 & M=13 is a special case
if(n==13 && m==11) return 6;
if(m==13 && n==11) return 6;
// If the given rectangle is
// already a square
if (m == n)
return 1;
// If the answer for the given
// rectangle is previously
// calculated return that answer
if (dp[m][n] != 0)
return dp[m][n];
/* The rectangle is cut horizontally
and vertically into two parts and
the cut with minimum value is found
for every recursive call.
*/
for (let i = 1; i <= parseInt(m / 2, 10); i++)
{
// Calculating the minimum answer
// for the rectangles with width
// equal to n and length less than
// m for finding the cut point for
// the minimum answer
horizontal_min
= Math.min(minimumSquare(i, n)
+ minimumSquare(m - i, n),
horizontal_min);
}
for (let j = 1; j <= parseInt(n / 2, 10); j++) {
// Calculating the minimum answer
// for the rectangles with width
// less than n and length equal to
// m for finding the cut point for
// the minimum answer
vertical_min
= Math.min(minimumSquare(m, j)
+ minimumSquare(m, n - j),
vertical_min);
}
// Minimum of the vertical cut or
// horizontal cut to form a square
// is the answer
dp[m][n] = Math.min(vertical_min, horizontal_min);
return dp[m][n];
}
let m = 30, n = 35;
// Function call
document.write(minimumSquare(m, n));
// This code is contributed by divyesh072019.
</script>
5
Complejidad temporal: O(N * M * (N + M))
Complejidad espacial: O(N * M)
Este artículo es una contribución de Ayush Govil , Aditya Nihal Kumar Singh y Deepanshu Aggarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA