¿Conjunto óptimo de tamaños de rectángulo para empaquetar rectángulo arbitrario?

Question

Yo estoy buscando para construir un conjunto de cajas de almacenamiento de madera de varios tamaños estándar para el almacenamiento de objetos pequeños.

Me gustaría elegir un conjunto de "óptima" cuadro de tamaños (dimensiones exteriores) para el relleno arbitraria de los espacios rectangulares.

Yo defino "óptima" aquí:

• minimizar el desperdicio de espacio después de la colocación;

• minimizar los diferentes tamaños de caja; y

• minimizar el número de cajas necesarias para llenar el espacio, asumiendo la definición de algunos de los más grandes de la casilla de dimensión.

En 1 dimensión, esto es sencilla: un conjunto de "cajas" de los tamaños { 16, 8, 4, 2, 1 } puede llenar cualquier 1-dimensional espacio con menos de 1 unidad de residuos con mi definición de "óptima" como es arriba.

2-dimensiones de los espacios, no sé cómo resolver esto. Parece que debe haber algún geométricas respuesta a esto, pero no estoy lo suficientemente versado en el embalaje de los problemas para saber por dónde empezar a buscar.

Me preguntaba si alguien de aquí podría ayudar a resolver esto, o señalar el camino a una respuesta?

Gracias!

Answer 1

Aunque no necesita todas las propiedades de esta partición en particular basadas en números triangulares, podría considerar usarla o una partición análoga:

---

^{Imagen de Wikipedia .}

---

Answer 2

No estoy seguro de si esta es la óptima, pero funciona.

Mi colección optimiza "no se desperdicia espacio", y también minimiza el número de cajas necesarias en el sentido de que "el más eficiente de baldosas de cualquier espacio" se obtiene mediante el más grande de los cuadros de primera. Sin embargo, usted puede sentir que hay demasiadas cajas.

Para $2$-dimensiones del espacio, yo uso $(x,y)$ para denotar rectángulos con las longitudes de los lados $x$ e $y$.

1. $\{(1,1), (1,2), (1,2), (2,2)\}$ va a llenar todos los espacios (con el entero lados) a $3\times 3$ sin huecos (con el algoritmo voraz)
2. $\{(1,1),(1,2),(1,2),(1,4),(1,4),(2,2),(2,4),(2,4),(4,4)\}$ va a llenar todos los espacios con el entero lados hasta $7\times 7$ sin huecos (con el algoritmo voraz)

De manera más general, las colecciones de las cajas están definidos por:

uno de cada caja de tamaño $(x,x)$, dos de cada caja de tamaño $(x,y)$ con $x\neq y$, donde $x,y \in \{1,2,4,8,...\}$.

Suponemos que la colección de cuadros generados de esta manera siempre azulejo más grande 2d espacios sin huecos utilizando el algoritmo voraz. (He comprobado esto para los dos casos anteriores, pero no, por ejemplo, $15\times 15$, $31\times 31$,...)

"Utilizando el algoritmo voraz", me refiero a que si intenta azulejo algo de espacio, sólo tienes que iniciar con la mayor caja, a continuación, utilizar el segundo más grande de la caja, etc.

Sospecho que tal vez sea más óptima solución que hace uso de golden ratio-eqsue matemáticas.