algorithm - 这是什么算法？分配有限资源的最佳方式

Question

我最近在一个编程挑战中看到这个问题，我想知道这类似于哪个著名的 CS 算法。我实现了一个粗略的解决方案。我知道一定有更好的方法来做到这一点，但我不确定要搜索的术语。它似乎像是背包问题的一个变体……但有足够多的差异让我有点困惑。

问题:

有 3 个城市(A、B、C)的人口为(100、100、200)。您可以 build 4 家医院。 build 医院，尽量减少每家医院的就诊人数。

在这个例子中，答案是:在 A 中 build 1 个，在 B 中 build 1 个，在 C 中 build 2 个。这意味着每家医院为 100 人提供服务(最佳解决方案)。

例如，如果您要将医院分布为 A 中 1 家、B 中 2 家和 C 中 1 家，您将取平均值 (100, 50, 200)，这给出了最坏情况 200(不是最佳情况)解决方案)。

谢谢。

附录:

• 为了简化问题，医院的数量总是>= 城市的数量。每个城市应该至少有 1 家医院。

Answer 1

1. 为每个城市分配一家医院
2. 医院离开时
3. 计算出每个城市的人口与医院比率
4. 将医院分配给比率最高的医院
5. 循环