3

有一组 9 个学生和 3 个学校 每个学校最多可以分配 3 个学生。每个学校和学生都有自己的坐标。现在我们必须以这样的方式分配学生，即所有学生到学校的距离总和应该是最小的。

我在一次采访中被问到这个问题。有人可以为此建议一个算法吗？

最初我尝试了贪婪的方法，但这不起作用。然后我尝试应用动态编程方法，但无法提出最佳的子结构。

4

2 回答 2

4

每所学校有3个名额，3所学校都有9个名额。你应该找到 9 个地方和 9 个学生之间的最佳匹配。

这个分配问题可以用匈牙利算法来解决。

于 2012-11-12T18:25:48.130 回答
1

由于问题规模足够小，如何进行穷举搜索？

  • 第一所学校从 9 名学生中选择 3 名开始。
  • 第二所学校从剩下的 6 名学生中选择 3 名。
  • 最后一所学校被剩下的 3 名学生困住了。

所以(9 choose 3) * (6 choose 3) = 1680

于 2012-11-12T18:44:20.707 回答