- Objeto que se empaqueta
- Cabe
- No cabe
Problema de empaquetado (bin packing)
Cajas en furgonetas, archivos en discos, tareas en máquinas: el problema de empaquetado, o bin packing, pregunta cómo meter una lista de objetos en el menor número posible de contenedores iguales. No se conoce ningún método rápido que encuentre siempre el mejor empaquetado, pero hay reglas sencillas que se acercan mucho. Elige una regla, recórrela paso a paso y compárala con la respuesta exacta. Toca un objeto del estante y luego toca un contenedor para meterlo: los contenedores verdes tienen sitio para él, y Nuevo contenedor abre otro. Toca un objeto de un contenedor para sacarlo otra vez. Empaqueta todos los objetos en los menos contenedores que puedas; la cota inferior (el peso total dividido entre el tamaño del contenedor, redondeado hacia arriba) y el mínimo posible muestran lo cerca que estás, y Mínimo de contenedores muestra el mejor empaquetado. Cambia los pesos de los objetos (en kilogramos) y el tamaño del contenedor en el panel. La vista Paso a paso muestra cómo empaquetan las reglas rápidas: Next Fit, First Fit o Best Fit, con los objetos en el orden escrito u ordenados de mayor a menor, o la respuesta exacta hallada por programación dinámica. Pulsa Reproducir para ver cómo entran los objetos en los contenedores, o Paso y Atrás para avanzar paso a paso, y arrastra el control de pasos para saltar a cualquier punto. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Toca un objeto y luego un contenedor con sitio para meterlo, o Nuevo contenedor para abrir otro.
- Intenta usar el menor número de contenedores, o pulsa Mínimo de contenedores para ver el mejor empaquetado.
- Abre la vista Paso a paso, elige una regla y pulsa Reproducir para ver cómo cada objeto prueba los contenedores.
Las reglas
Next Fit solo mantiene abierto el último contenedor: un objeto que no cabe en él empieza un contenedor nuevo. First Fit prueba los contenedores desde el primero y elige el primero con sitio. Best Fit prueba todos los contenedores y elige el más lleno que tenga sitio, con lo que deja sin usar el menor espacio posible. First Fit y Best Fit también pueden ordenar antes los objetos de mayor a menor, y así se obtienen First Fit Decreasing y Best Fit Decreasing.
La respuesta exacta
La última regla no es una regla práctica aproximada: encuentra el mínimo de contenedores por programación dinámica sobre los conjuntos de objetos. Para cada conjunto de objetos guarda el menor número de contenedores que los contienen y, entre los empaquetados con ese número de contenedores, la menor carga en el último contenedor. Un conjunto crece de objeto en objeto, y cada uno completa el último contenedor o abre uno nuevo. Con n objetos hay 2ⁿ conjuntos, y por eso la aplicación admite como mucho 12 objetos. La cota inferior, es decir, el tamaño total dividido entre el tamaño del contenedor y redondeado hacia arriba, muestra lo cerca que está un empaquetado del mejor.
Preguntas frecuentes
¿Qué regla de empaquetado es la mejor?
De las reglas rápidas, First Fit Decreasing y Best Fit Decreasing son las más fuertes: nunca usan más de 11/9 del mínimo de contenedores, más una pequeña constante. First Fit y Best Fit con objetos sin ordenar se quedan dentro de 1,7 veces el mínimo de contenedores, y Next Fit dentro de 2 veces.
¿Por qué es difícil el problema de empaquetado?
Decidir si los objetos caben en solo dos contenedores ya es el problema de la partición, que es NP-completo. Así que, a menos que P = NP, ningún método encuentra rápido el mínimo de contenedores para cualquier entrada, y los métodos exactos tardan un tiempo exponencial en el peor caso.
¿Qué es la cota inferior?
El tamaño total de los objetos dividido entre el tamaño del contenedor, redondeado hacia arriba. Ningún empaquetado puede usar menos contenedores, porque los contenedores tienen que contener todos los objetos. A menudo el mejor empaquetado la alcanza, pero no siempre: tres objetos de tamaño 6 con contenedores de 10 tienen una cota inferior de 2 y necesitan 3 contenedores.
¿Esto es programación dinámica?
La respuesta exacta sí: construye el mejor empaquetado de cada conjunto de objetos a partir de los mejores empaquetados de conjuntos más pequeños. Las reglas rápidas son métodos voraces, que deciden una vez y nunca vuelven atrás.
¿Se envía algo a algún sitio?
No. Todo se calcula en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor