¿Cuál es el nombre/algoritmo correcto del problema para la descripción de este problema en la teoría de la informática?

El problema es que tengo X elementos de valores ponderados variables que deben ir en contenedores Y. Los contenedores son de diferentes tamaños (por ejemplo, tienen diferentes pesos máximos). La carga total de cada contenedor debe ser aproximadamente equivalente a las demás, pero los contenedores no necesitan estar llenos o minimizados. Todos los contenedores deben ser usados.¿Cuál es el nombre/algoritmo correcto del problema para la descripción de este problema en la teoría de la informática?

Esto me recuerda el problema de la mochila, pero tengo varias mochilas de diferentes tamaños y las cargas entre ellas deben ser relativamente equivalentes (por ejemplo, una mochila solo puede contener 12 libras y otra mochila solo puede contener 8 libras , pero ambos deben llenarse con el mismo porcentaje de peso total que pueden llevar). También me recuerda el problema del "contenedor de basura", pero eso no se relaciona con los diferentes tamaños de contenedores o que los contenedores no necesitan estar llenos o minimizados, solo necesitan cargas equivalentes y todos deben ser utilizados. .

¿Alguien puede indicarme en la dirección correcta el nombre de este problema dentro de las estructuras de datos y la teoría de algoritmos? También me interesaría cualquier algoritmo o heurística que pueda usarse comúnmente para resolver un problema como este o información sobre la posible complejidad temporal.

Fuente

2010-12-11 aoeu

problema de mochila o problema de embalaje –

Definitivamente está en la clase de problemas de optimización, pero es una generalización del problema de mochila (en cuyo caso puede tener mejor nombre), no el problema de mochila en sí, y el problema de embalaje suele ser para optimizar al mínimo con un conjunto uniforme de objetos, esto minimiza la desviación estándar con un conjunto heterogéneo de objetos. –

Tenga en cuenta: este no es un problema de "tarea" o tal. Es un problema real del "mundo real" para el que necesito codificar una solución, pero estoy teniendo dificultades para diseñar un algoritmo efectivo por mi cuenta o para encontrar una descripción de problema similar. – aoeu

Suena como una mochila múltiple para mí. De Wikipedia:

Si tenemos n elementos y m mochilas con capacidades Wi, obtenemos el problema de la mochila múltiples

EDIT: Lo sentimos, se perdió el poco acerca de cada contenedor que necesita ser cargado de manera similar. Aún así, huele a como multiple-knapsack, aunque con una restricción adicional.

Fuente

2010-12-11 03:22:36

Y menos uno, sin embargo. Estoy de acuerdo en que me duele, como en la mochila múltiple, pero la mochila tiene objetos bidimensionales con costos (o tamaño) y valores asociados, donde se optimiza para máximo (valor), mínimo (costo); esto se está optimizando para una desviación estándar máxima sobre el conjunto de mochilas, con solo objetos unidimensionales (tamaño asociado). –

Si asigna X a imágenes de diferentes alturas; y mapee Y a las columnas, entonces la solución dada here debería funcionar para usted también. Se trata de una solución de envasado de contenedores que presenta el peor ajuste, con preclasificación y cambio de artículo adicional codificado en Python con ejemplos.

Fuente

2011-05-19 21:13:02 Paddy3118

¿Cuál es el nombre/algoritmo correcto del problema para la descripción de este problema en la teoría de la informática?

Respuesta

Cuestiones relacionadas