algorithm - voraz - problema de la mochila winqsb

Diseño del algoritmo: ¿puede proporcionar una solución al problema de la mochila múltiple?

Question

Estoy buscando una solución de pseudocódigo para lo que es efectivamente el Problema Múltiple de Mochila (la declaración de optimización está en la mitad de la página). Creo que este problema es NP completo, por lo que la solución no necesita ser óptima, sino que si es bastante eficiente y fácil de implementar sería bueno.

El problema es este:

• Tengo muchos elementos de trabajo, y cada uno toma una cantidad de tiempo diferente (pero fija y conocida) para completar.
• Necesito dividir estos elementos de trabajo en grupos para tener el menor número de grupos (idealmente), con cada grupo de elementos de trabajo ocupando no más de un umbral total dado, digamos 1 hora.

Soy flexible con respecto al umbral; no es necesario aplicarlo de manera rígida, aunque debe ser cercano. Mi idea era asignar elementos de trabajo en contenedores donde cada contenedor representa el 90% del umbral, el 80%, el 70% y así sucesivamente. Entonces podría unir elementos que llevan un 90% con aquellos que toman un 10%, y así sucesivamente.

Alguna mejor idea?

Answer 1

Hasta donde yo sé, el problema es NP completo (Wikipedia confirma ), por lo que probablemente no tenga mucho sentido intentar resolverlo exactamente. Sin embargo, cualquier cantidad de enfoques puede ser lo suficientemente bueno para usted: codiciosos algoritmos genéticos, simulación de recocido ... codicioso es probablemente el más fácil de implementar:

while (time available in block greater than smallest task duration)
  find the longest fitting task
  add it

... entiendes la idea.

Answer 2

Necesita http://www.or.deis.unibo.it/knapsack.html , capítulo 6.6 "Problema de varios knapscack - Algoritmos aproximados". Hay un pseudocódigo (estilo Pascal) en el texto y las implementaciones de Fortran (sí, es un libro antiguo) como un archivo ZIP.