Distance minimum

Question

Il y a un ensemble de 9 étudiants et 3 écoles Chaque école peut être attribuée à maximum 3 étudiants. Chaque école et chaque élève a ses coordonnées. Maintenant, nous devons répartir les étudiants de telle sorte que la somme de la distance de tous l'étudiant à l'école devrait être minimum.

On m'a posé cette question dans une interview. Quelqu'un peut-il suggérer un algorithme pour cela? Au début, j'ai essayé l'approche gourmande, mais cela ne fonctionne pas. Ensuite, j'ai essayé d'appliquer une approche de programmation dynamique, mais je n'ai pas réussi à trouver une sous-structure optimale.

Answer 1

Chaque école a 3 places, les 3 écoles ont 9 places. Et vous devriez trouver le meilleur match entre 9 places et 9 étudiants.

Ce problème d'affectation peut être résolu avec Hungarian algorithm.

Answer 2

Que diriez-vous de la recherche exhaustive puisque la taille du problème est assez petite?

• La première école choisit 3 élèves sur 9 pour commencer.
• La deuxième école choisit 3 élèves sur 6 restants.
• Dernière école coincé avec les 3 étudiants restants.

Alors (9 choose 3) * (6 choose 3) = 1680