有一组9名学生和3所学校每所学校最多可以分配3名学生。每所学校和学生都有其坐标。现在我们必须以与所有学生的距离之和的方式分配学生对学校的影响应该是最小的。
我在面试中被问到这个问题。有人可以为此推荐一个算法吗？
最初我尝试了贪婪的方法，但那不起作用。然后我尝试应用动态规划方法，但无法提出最佳子结构。
最佳答案
每所学校有3个名额，所有3所学校都有9个名额。你应该找到 9 个位置和 9 个学生之间的最佳匹配。
这个赋值问题可以用Hungarian algorithm来解决。 .
关于algorithm - 最小距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13349164/