Hay un conjunto S que contiene N enteros, cada uno con valor 1 <= X <= 10 ^ 6. El problema es dividir el conjunto S en k particiones. El valor de una partición es la suma de los elementos presentes en ella. La partición debe hacerse de tal manera que el valor total del conjunto S se distribuya equitativamente entre las k particiones. El significado matemático dejust también necesita ser definido (por ejemplo, el objetivo podría ser minimizar la desviación estándar de los valores de las particiones del valor promedio del conjunto S (que es, suma (S) / k))

p.ej. S = {10, 15, 12, 13, 30, 5}, k = 3

Una buena partición sería {30}, {10, 15}, {12, 13, 5}

Una partición incorrecta sería {30, 5}, {10, 15}, {12, 13}

a primera pregunta es expresar matemáticamente la condición para que una partición sea mejor que la otra. La segunda pregunta es cómo resolver el problema. El problema es NP-Hard. ¿Hay alguna heurística?

En el problema que estoy tratando de resolver N <= (k * logX) ^ 2 y K varía de 2 a 7.

================================================= =================================

Basado en otras preguntas SO relacionadas, hay dos funciones razonables para evaluar una distribución:

a) Minimice el valor de la partición con el valor máximo.

Pensándolo bien, esta no es una buena métrica. Considere un conjunto {100, 40, 40} que se dividirá en tres subconjuntos. Esta métrica no distingue entre las siguientes dos distribuciones, aunque una es claramente mejor que la otra.

Distribución 1: {100}, {40}, {40} y Distribución 2: {100}, {40, 40}, {}

b) Minimice el máximo de la diferencia de cualquiera de los dos valores en una partición dada, es decir, minimice max | A-B | para cualquier A, B