Rellenar una caja con cubos de tamaño potencia de 2 con la menor cantidad de cajas posible

Question

Digamos que tengo una caja con dimensiones enteras y necesito llenarla con cubos con longitudes de lado de potencia de 2, ¿cómo puedo llenar completamente la caja con la menor cantidad de cubos posible? Así que digamos que tengo una caja de $5 \times 5 \times 9$, ¿cómo lleno el espacio con la menor cantidad de cubos posible (las opciones en este caso incluirían cubos con longitudes de lado: 1, 2, 4)? Estoy buscando una explicación general, no solo la respuesta a este ejemplo

Answer 1

Puedes resolver esto como un problema de partición de conjuntos mediante programación lineal entera de la siguiente manera. Deja que $\ell$, $w$ y $h$ sean las dimensiones de la caja. Deja que $C$ sea el conjunto de todos los posibles cubos que tienen un lado que es una potencia de $2$ y pueden caber en la caja. Deja que $C_{i,j,k}\subset C$ sea el conjunto de cubos que contienen la celda $(i,j,k)\in [\ell] \times [w] \times [h]$. Para $c\in C$, deja que la variable de decisión binaria $x_c$ indique si se usa el cubo $c$. El problema es minimizar $\sum_{c\in C} x_c$ sujeto a restricciones lineales $$\sum_{c\in C_{i,j,k}} x_c = 1 \quad \text{para todo $(i,j,k) \in [\ell] \times [w] \times [h]$}$$ que obligan a que cada celda unitaria en la caja esté cubierta por exactamente un cubo en $C$.

Para $(\ell,w,h)=(5,5,9)$, tenemos $|C|=377$, y el valor objetivo óptimo resulta ser $99$, alcanzado al usar dos cubos de lado $4$ (por ejemplo, con esquinas $(2,2,1)$ y $(2,2,5)$, respectivamente) y $5\cdot5\cdot9 - 2\cdot 4^3 = 225 - 128 = 97$ cubos unitarios, como sugirió @ThomasAndrews.