Algoritmo para obtener el tamaño máximo de n cuadrados que caben en un rectángulo con un determinado ancho y la altura

Question

Estoy buscando un algoritmo que puede devolver el número de tamaño de n cuadrados que caben en un rectángulo de una determinada anchura y la altura, para maximizar el uso de espacio (por lo tanto, dejando la menor cantidad de restos de espacio para las plazas que no se ajustan). Ni el rectángulo ni las plazas se pueden girar.

Por ejemplo, digamos que tengo un rectángulo que es de 5 pulgadas por 7 pulgadas, y la necesito para adaptarse a 35 plazas. El algoritmo necesita para decirme que el 35 plazas ajuste si son de 1 pulgada de ancho/alto (como podrían ser colocados en el interior del rectángulo en una cuadrícula de 5 x 7). Otro ejemplo es si necesito dividir un rectángulo de 35 pulgadas por 1 pulgada de 35 plazas. Todavía me dicen que las plazas se ajuste a si son de 1 pulgada de ancho/alto (como podrían ser establecidos en el rectángulo en un 35 x 1 red).

La parte difícil es que a veces no puede ser de sobra espacio, como las plazas no puede ser dividido en parcial plazas. Digamos que para cualquiera de los dos ejemplos anteriores he necesidad de disponer de 34 plazas y no 35 (en cuyo caso las respuestas podría ser 1 pulgada), o tal vez de 33 años, o 7 plazas. O, tal vez el rectángulo de anchura y altura no son números enteros. Con el número de plazas de ser una variable necesito un algoritmo que me puede decir el tamaño de los cuadrados para un determinado rectángulo de anchura y altura.

Gracias por su ayuda!

Answer 1

Vamos a analizar un caso único:

Si queremos cubrir una $6x5$ rectángulo con $7$ plazas, en primer lugar tenga en cuenta que cada cuadrado en la mayoría cuenta con una superficie de $30/7$. También sabemos que para nuestro relleno de ser óptimo, tenemos que rellenar al menos un eje.

Así que ahora sabemos que vamos a llenar el $6$ o de la $5$ completamente. Vamos a probar primero con el 5. Desde la máxima lado de nuestras plazas es $\sqrt{30/7}$, lo que necesitamos ahora es el entero más pequeño mayor que $5/\sqrt{30/7}$, que es igual a $\lceil5/\sqrt{30/7}\rceil=3$

De modo que podemos dividir el $5$ $3$ partes $p_x$, de modo que cada lado se ha $5/3$ . Si es así, me cubriría $(5/3)^2*7=19\frac49$ de las treinta plazas. Si no se ajustan verticalmente, tratamos con más piezas de $p_x$, hasta las plazas de ajuste en el otro eje. $$\lfloor6/(5/p_x)\rfloor*\lfloor5/(5/p_x)\rfloor=\lfloor6/(5/p_x)\rfloor*p_x\ge7 \,\,\,\,\,\,\,\,\,\, (5/p_x=\text{the actual size of our squares)}$$ También, desde la $p_x$ es entero $\lfloor p_x \rfloor =p_x$

Si hacemos lo mismo con el $6$, obtenemos $\lceil6/\sqrt{30/7}\rceil$ vez que cubre $19\frac49$ de la superficie. Entonces, hacemos lo mismo que con el $5$ y guárdelo como $p_y$

Ahora vamos a recordar las fórmulas que hemos tenido.

Tuvimos una $x∗y$ rectángulo y lo llenó con $N$ plazas. Empezamos con $p_x=⌈x/\sqrt{xy/N}⌉$=$⌈\sqrt{Nx/y}⌉$ o $p_y=⌈y/\sqrt{xy/N}⌉=⌈\sqrt{Ny/x}⌉$ y, a continuación, les hicimos ajuste por reducción de ellos hasta que se ajuste en el otro eje. Pero sabemos que tenemos que desea que el área de maximizada, por lo $Side=max(x/p_x,y/p_y)$.

Un método mejor:

Una vez que tenemos el valor de inicio $p_x=⌈x/\sqrt{xy/N}⌉=⌈\sqrt{Nx/y}⌉$,si no encaja en el $y$ eje, tenemos que hacer que encaje en el $y$ eje. Para ello, utilizamos que $$a=x/p_x$$ donde $a$ es el valor real del lado de nuestras plazas. Sabemos que para nuestro lado para que se ajuste necesitamos reducir: $$S_x=y/(\lceil y/a \rceil)$$ Lo mismo hacemos con el $S_y$ y calcular el $max(S_x,S_y)$ La ventaja de esto es que se necesita un número constante de operaciones, el más caro de ser la raíz cuadrada.

Llanura, unoptimized Código C

Algunas multiplicaciones pueden ser reutilizados, pero para la legibilidad del código y usos prácticos esto es suficiente. Entrada: valores de $x$,$y$, y $n$. Handcoded.

Salida: El óptimo lado de nuestras plazas

#include <math.h>
#include <stdio.h>
#define MAX(x,y)    (x)>(y)?(x):(y) 
int main(){
    double x=5, y=6, n=7;//values here
    double px=ceil(sqrt(n*x/y));
    double sx,sy;
    if(floor(px*y/x)*px<n)  //does not fit, y/(x/px)=px*y/x
            sx=y/ceil(px*y/x);
    else
            sx= x/px;
    double py=ceil(sqrt(n*y/x));
    if(floor(py*x/y)*py<n)  //does not fit
            sy=x/ceil(x*py/y);
    else
            sy=y/py;
    printf("%f",MAX(sx,sy));
    return 0;
}