C# Algoritmo per determinare il raggruppamento di persone in base a un valore

Question

Sto tentando di scrivere un algoritmo che crea gruppi di persone in base al loro "punteggio". Una persona ha due parametri, un nome e un punteggio. (L'intervallo del punteggio è compreso tra -10 e 10 ma non è rilevante) Sto cercando di creare gruppi con un numero uguale di persone (se possibile in base al numero di persone presentate) in cui il punteggio medio dei membri del gruppo è lo stesso (o molto vicino allo stesso).

Ad esempio:

Gruppo 1 (Punteggio medio = 2) - John Doe, Punteggio 2 - Jane Doe, Clienti 7 - Jack Black, Score -3

Gruppo 2 (Punteggio medio = 2) - Bobby Flay, Score 4 - Cary pagina, il punteggio -3 - Linus Tarval, Score 5

Answer 1

Questa puzza come una variante della classica Partition Problem, che è NP-hard anche se alcune euristiche e xists. Puoi avere un bottino nella pagina di Wikipedia ... probabilmente un approccio avido potrebbe funzionare nel tuo caso.

Dovresti provare a riempire i tuoi gruppi scegliendo il gruppo giusto per posizionare una persona specifica, probabilmente iniziando a ordinarli per punteggio.

Answer 2

Questo è un problema difficile. Il migliore che tu possa fare è un euristico, ma k-means è buono: http://en.wikipedia.org/wiki/K-means_clustering