Estoy buscando una solución de pseudocódigo para lo que efectivamente esProblema de mochila múltiple (la declaración de optimización está a la mitad de la página). yopensar este problema es NP Complete, por lo que la solución no necesita ser óptima, si es bastante eficiente y fácil de implementar, sería bueno.

El problema es este:

Tengo muchos elementos de trabajo, y cada uno requiere 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 que no tome más de un umbral total dado, digamos 1 hora.

Soy flexible con respecto al umbral: no es necesario que se aplique de manera rígida, aunque debe estar cerca. Mi idea era asignar elementos de trabajo i, nto bins donde cada bin representa el 90% del umbral, 80%, 70% y así sucesivamente. Entonces podría hacer coincidir los elementos que toman el 90% con los que toman el 10%, y así sucesivamente.

¿Alguna idea mejor?