Problema de empaquetado
El objetivo es empaquetar un solo contenedor lo más densamente posible o empaquetar todos los objetos usando la menor cantidad de contenedores posible.
Cada problema de empaque tiene un problema de doble cobertura, que pregunta cuántos de los mismos objetos se requieren para cubrir completamente cada región del contenedor, donde los objetos pueden superponerse.
En un problema de embalaje en contenedores, se proporciona: Por lo general, el embalaje no debe tener superposiciones entre las mercancías y otras mercancías o las paredes del contenedor.
En algunas variantes, el objetivo es encontrar la configuración que empaqueta un solo contenedor con la máxima densidad.
[1] En algunas variantes, la superposición (de objetos entre sí y/o con el límite del contenedor) está permitida, pero debe minimizarse.
Muchos de estos problemas, cuando el tamaño del contenedor aumenta en todas las direcciones, se vuelven equivalentes al problema de empaquetar objetos lo más densamente posible en un espacio euclidiano infinito.
Este problema es relevante para varias disciplinas científicas y ha recibido una atención significativa.
Las contrapartes de un círculo en otras dimensiones nunca pueden empaquetarse con total eficiencia en dimensiones mayores a uno (en un universo unidimensional, el círculo análogo son solo dos puntos).
Es decir, siempre habrá espacio no utilizado si solo está empacando círculos.
[9] La celosía E8 de 8 dimensiones y la celosía Leech de 24 dimensiones también han demostrado ser óptimas en su respectivo espacio dimensional real.
Los cubos se pueden organizar fácilmente para llenar completamente el espacio tridimensional, siendo el empaque más natural el panal cúbico.
El empaquetado en tetraedros puede lograr un empacado de al menos el 85 %.
El tetraedro y el octaedro juntos pueden llenar todo el espacio en una disposición conocida como panal tetraédrico-octaédrico.
Las simulaciones que combinan métodos de mejora local con empaques aleatorios sugieren que los empaques de celosía para icosaedros, dodecaedros y octaedros son óptimos en la clase más amplia de todos los empaques.
[3] Determinar la cantidad mínima de contenedores cuboides (contenedores) que se requieren para empacar un conjunto dado de artículos cuboides (rectángulos tridimensionales).
El problema de encontrar la bola más pequeña tal que
bolas separadas de la unidad abierta se pueden empaquetar dentro tiene una respuesta simple y completa en
Vale la pena describirlo en detalle aquí para dar una idea del problema general.
simplex dimensional con borde 2; esto se realiza fácilmente partiendo de una base ortonormal.
Un pequeño cálculo muestra que la distancia de cada vértice desde el baricentro es
Para demostrar que esta configuración es óptima, sea
este mapa es 1-Lipschitz y por el teorema de Kirszbraun se extiende a un mapa 1-Lipschitz que está definido globalmente; en particular, existe un punto
es una base ortonormal, son disjuntos y se incluyen en una bola de radio
Determinar la altura mínima h de un cilindro con un radio R dado que empacará n esferas idénticas de radio r (< R.[12] Para un radio pequeño R, las esferas se organizan en estructuras ordenadas, llamadas estructuras columnares.
Determinar el radio mínimo R que empacará n poliedros de volumen unitario idénticos de una forma dada.
Dados n círculos unitarios, se debe empacarlos en el recipiente más pequeño posible.
Se han estudiado varios tipos de envases: Dados n cuadrados unitarios, se debe empacarlos en el contenedor más pequeño posible, donde el tipo de contenedor varía: En los problemas de mosaico o teselado, no debe haber espacios ni superposiciones.
Muchos de los acertijos de este tipo implican empaquetar rectángulos o poliominós en un rectángulo más grande u otra forma cuadrada.
Un rompecabezas clásico del segundo tipo consiste en organizar los doce pentominós en rectángulos de tamaño 3×20, 4×15, 5×12 o 6×10.
El empaquetado de objetos irregulares es un problema que no se presta bien a soluciones de forma cerrada; sin embargo, la aplicabilidad a la ciencia ambiental práctica es bastante importante.
