El problema de empaquetado

En una mudanza llenas una caja tras otra y te preguntas si con un orden más inteligente habrían hecho falta menos. Ese es el problema de empaquetado, y es famoso por lo difícil que es: incluso los ordenadores solo encuentran el mínimo de contenedores para entradas grandes con búsquedas ingeniosas. Aun así, las reglas sencillas se acercan sorprendentemente.

Contenedores de la misma altura llenos de objetos de colores apilados de distintos tamaños, con más objetos esperando encima
Contenedores de la misma altura llenos de objetos de colores apilados de distintos tamaños, con más objetos esperando encima

El problema

Dados unos objetos con sus tamaños y unos contenedores que admiten todos la misma cantidad, hay que meter cada objeto en un contenedor sin que ninguno se desborde, usando el menor número posible de contenedores. Los tamaños pueden representar pesos, longitudes, duraciones o tamaños de archivo. Parece un pasatiempo para una tarde de lluvia, pero es NP-difícil: no se conoce ningún método que encuentre rápido el mínimo de contenedores para cualquier entrada.

Reglas rápidas

Next Fit llena un contenedor hasta que el siguiente objeto no cabe, entonces empieza uno nuevo y nunca vuelve atrás. First Fit mantiene abiertos todos los contenedores y mete cada objeto en el primer contenedor con sitio. Best Fit mete cada objeto en el contenedor más lleno que aún tenga sitio. Las tres deciden al momento, lo que resulta útil cuando los objetos llegan de uno en uno y hay que colocarlos enseguida.

Primero, ordenar

Los objetos grandes son los difíciles, porque necesitan mucho espacio libre. Ordenar los objetos de mayor a menor y luego usar First Fit o Best Fit mete los grandes mientras los contenedores siguen vacíos, y los pequeños rellenan los huecos. First Fit Decreasing nunca usa más de 11/9 del mínimo de contenedores, más una constante, frente a 1,7 veces de First Fit con objetos sin ordenar.

Un ejemplo

Toma contenedores de tamaño 10 y los objetos 2, 3, 2, 1, 3, 4, 5, 6, 7 y 7, que suman 40. First Fit mete 2, 3, 2 y 1 en el primer contenedor y 3 y 4 en el segundo, y luego 5, 6, 7 y 7 necesitan cada uno su propio contenedor: 6 contenedores. Ordenados de mayor a menor, First Fit Decreasing forma 7 + 3, 7 + 3, 6 + 4 y 5 + 2 + 2 + 1: 4 contenedores llenos, que coinciden con la cota inferior de 40 / 10 = 4.

Encontrar el mínimo de contenedores

Con pocos objetos, la respuesta exacta se puede hallar por programación dinámica sobre subconjuntos: para cada conjunto de objetos, el mínimo de contenedores y el último contenedor más vacío que lo contienen, construidos a partir de los conjuntos con un objeto menos. Eso lleva unos 2ⁿ·n pasos para n objetos. Los casos más grandes se resuelven con ramificación y poda o con programación entera, y la cota inferior indica lo lejos del mejor que puede estar un empaquetado.

Dónde se usa

Cargar camiones y contenedores, cortar tubos o bobinas de papel de longitudes estándar con el menor desperdicio posible (el problema de corte), repartir máquinas virtuales entre servidores y guardar archivos en discos son todos problemas de empaquetado. En dos y tres dimensiones, con cajas en lugar de números, el problema es aún más difícil.

Preguntas frecuentes

¿Qué diferencia hay entre el empaquetado en línea y fuera de línea?

En línea, cada objeto se tiene que colocar en cuanto llega, sin conocer los demás; así funcionan Next Fit, First Fit y Best Fit. Fuera de línea, todos los objetos se conocen de antemano, así que se pueden ordenar primero, como hace First Fit Decreasing.

¿Cuánto se acerca First Fit Decreasing al mínimo?

Usa como mucho 11/9 del mínimo de contenedores más 6/9 de contenedor, una cota que György Dósa demostró que es exacta en 2007. Con entradas típicas suele ser óptimo o quedarse a un contenedor.

¿El problema de empaquetado es lo mismo que el problema de la mochila?

Están relacionados, pero son distintos. La mochila llena una sola bolsa con los objetos más valiosos; el empaquetado mete todos los objetos en el menor número posible de bolsas. Los métodos exactos de empaquetado suelen funcionar resolviendo una y otra vez problemas parecidos al de la mochila.

¿Por qué la aplicación solo admite 12 objetos?

Porque la respuesta exacta revisa cada conjunto de objetos, y 12 objetos ya forman 4096 conjuntos. Las reglas rápidas podrían con miles de objetos, pero el dibujo y la comparación con la respuesta exacta no.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Probar el empaquetado