Tengo una caja con algunas medidas de longitud, ancho y alto.Algoritmo de volumen de relleno
Tengo elementos con diferente longitud, ancho, alto.
¿Existe algún algoritmo que pueda determinar los mejores elementos para usar dentro de la caja?
Esto se conoce como un problema de embalaje/mochila de embalaje/corte, y es NP difícil. En general, sólo se puede obtener una solución aproximada mediante el uso de la heurística, véase por ejemplo
http://en.wikipedia.org/wiki/Knapsack_problem
No es de ellos. ¿Puedes explicar alguna aproximación? –
Todos estos algoritmos lo ayudan a optimizar el espacio ilimitado, al menos en una dimensión. Lo que se requiere es seleccionar el mejor ajuste de los elementos disponibles dadas las dimensiones de la caja finita. –
Probablemente no coincida con ninguno de ellos exactamente. Pero todos están estrechamente relacionados. P.ej. un contenedor de basura con un contenedor se convierte en otro problema. En la literatura, este tipo de problema generalmente se denomina "problema de embalaje tridimensional". Una búsqueda erudita arroja bastantes resultados http://scholar.google.com/scholar?q=box+packing+problem –
Esto quizás no es realmente una respuesta, pero creo que la respuesta es que el problema no tiene respuesta Sí, es una versión de un problema de embalaje. Pero eche un vistazo a la investigación de Erich Friedma en 2 dimensiones: Parece que el problema para los rectángulos de igual tamaño en cuadrados aún no se ha resuelto - ¡Observe la complejidad de algunas de estas soluciones!
http://www2.stetson.edu/~efriedma/squinsqu/
http://www2.stetson.edu/~efriedma/rigidrect/
(El problema se plantea de forma ligeramente diferente, es decir, cómo organizar mejor un cierto número de elementos para ocupar el menor espacio, en lugar de elegir qué elementos. Pero espero que su problema se reduce a la iteración de este tipo de cálculo sobre varias combinaciones de objetos)
y una variante 3-d que se ve muy parcialmente resuelto:. http://www2.stetson.edu/~efriedma/cubincub/
Es de suponer que su mejor apuesta es una heurística como sugiere Anders, aunque es casi seguro que no será óptima para casi todos los problemas. Curiosamente, la mayoría de las soluciones óptimas parecen ser altamente irregular, por lo que probablemente no las encontrarías.
Knapsack ¿Problema en forma de caja? –
Ese fue uno de los problemas de Maraton Match de TCO, si te registraste en TCO puedes encontrar una buena solución (no sé exactamente cuándo, pero creo que hace un año). el no de la solución es la respuesta exacta, todos intentan usar el recocido simulado y algo así. –