有限制的交货优化

Question

我有以下问题要解决：

1. 有N个城市。每个实验室都有一些需要在实验室进行处理的测试样本。
2. 有M个实验室。他们处理样品，但每一个都有限度。
3. 我们需要处理所有的样本。
4. 根据距离进行优化--试着在最近的实验室处理城市样品。

如果没有限制，这是很容易的-对每个城市，我们确定最近的实验室和用于处理样品。但是如果有容量限制，那么某些实验室可能会溢出，所以我们需要另找一个实验室来处理这个城市的样品(当然，这个实验室会更远一点)。

那么，的问题是：如何通过距离和不溢出来最优地分配样本流？

我相信这是一个很有名的算法。你能至少告诉我它叫什么吗？

谢谢!

Answer 1

试着把它看作是一个二部图，尝试使流量最大化：

排序城市和实验室之间的距离，从最近到最远，然后遍历列表，然后：

1. 把x样本从城市转移到实验室--在那里x=min(max_lab_capacity, number_of_samples)。
2. 城市和实验室之间的边缘现在被删除了。如果实验室是满的，那么实验室节点也会被删除。如果城市所有的样本都得到了处理--它的节点就会被删除。
3. 重复#1和#2，直到删除所有城市节点。