C# Algoritmo para determinar la agrupación de personas según un valor

Question

Estoy intentando escribir un algoritmo que crea grupos de personas en función de su "puntaje". Una persona tiene dos parámetros, un nombre y una puntuación. (El rango del puntaje está entre -10 y 10 pero eso realmente no es relevante). Estoy buscando crear grupos con igual número de personas (si es posible basado en el número de personas presentadas) donde el puntaje promedio de los miembros del grupo es lo mismo (o muy cerca de lo mismo).

Por ejemplo:

Grupo 1 (Puntuación Media = 2) - John Doe, Score 2 - Jane Doe, Puntuación 7 - Jack Negro, Score -3

Grupo 2 (Puntuación media = 2) - Bobby Flay, Score 4 - Cary página, el nivel -3 - Linus Tarval, Puntuación 5

Answer 1

Esto huele a una variación de la clásica Partition Problem, que es NP-Hard aunque algunas heurísticas e xists. Puedes tener un botín en la página de wikipedia ... probablemente un enfoque codicioso funcionaría en tu caso.

Debe intentar completar sus grupos eligiendo el grupo adecuado para colocar a una persona específica, probablemente comenzando con ordenarlos por puntaje.

Answer 2

Este es un problema difícil. Lo mejor que probablemente hará es una heurística, pero k-means es buena: http://en.wikipedia.org/wiki/K-means_clustering