使用贪心算法的最小化

Question

这里有一个问题，有n个房子在一条直线上，a1，...an。您希望构建这样的设施，即每个房屋与设施的最大距离为X。有p个地点b1，...bp，这些设施可以建造。我正在尝试一个贪婪的算法来计算出可以构建的最小设施数是多少。

我该如何着手解决这个问题呢？

Answer 1

对于每个位置(B1、...、Bp)，创建一个列表，其中包含距离该位置X距离内的房屋。

创建一个房屋列表(让我们将此列表称为"NeedToCover")，该列表最初包含所有房屋。

现在检查每个位置的列表，并确定哪个位置的列表覆盖了"NeedToCover“列表中最多的房屋。这将是您将在其中建立设施的位置。

在构建设施之后，删除"NeedToCover“中您刚刚选择的位置所覆盖的所有房屋。

对"NeedToCover“中的其余房屋和其余位置重复上述步骤，直到"NeedToCover”为空，这意味着所有房屋都在距离设施的X距离内。

(这种算法是贪婪的，因为每次您都是在“不考虑未来”的情况下从剩余的房屋中挑选覆盖最多房屋的位置。)