C# Algorithme pour déterminer le regroupement de personnes basé sur une valeur

Question

Je tente d'écrire un algorithme qui crée des groupes de personnes en fonction de leur «score». Une personne a deux paramètres, un nom et un score. (La fourchette de score est comprise entre -10 et 10 mais ce n'est vraiment pas pertinent) Je cherche à créer des groupes avec un nombre égal de personnes (si possible basé sur le nombre de personnes présentées) où le score moyen des membres du groupe est la même chose (ou très proche de la même chose).

Par exemple:

Groupe 1 (Note moyenne = 2) - John Doe, Score 2 - Jane Doe, Score 7 - Black Jack, score -3

Groupe 2 (Note moyenne = 2) - Bobby Flay, score 4 - Cary page Score -3 - Linus Tarval, Score 5

Answer 1

Cela sent comme une variante de la classique Partition Problem, qui est NP-dur bien que quelques heuristiques e xists. Vous pouvez avoir un butin à la page wikipedia .. probablement une approche gourmande fonctionnerait dans votre cas.

Vous devriez essayer de remplir vos groupes en choisissant le bon groupe pour placer une personne spécifique, probablement en commençant par les classer par score.

Answer 2

Ceci est un problème difficile. Le mieux que vous ferez probablement est une heuristique, mais k-means est un bon: http://en.wikipedia.org/wiki/K-means_clustering