我需要设计一种算法来解决以下问题：
考虑平面上的直线 L。有限的目标集 T 位于线 L 的上方，有限的无线传感器集 S 位于线 L 的下方。当且仅当 s 和 t 之间的欧几里德距离最多时，传感器 s 才能监视目标 t一。假设每个传感器 s ∈ S 具有正成本 c (s) 并且每个目标 t ∈ T 可以由 S 中的至少一个传感器监控。考虑 S 中传感器的子集 S0。如果每个T 中的目标被 S0 中的至少一个传感器覆盖。S0 的成本是 S0 中传感器的总成本。目标是计算最小成本的覆盖 S0。请开发一个多项式时间算法并编写一个程序来实现它。
我真的不知道我可以为此使用哪种类型的算法（贪婪、动态、分而治之）我并不一定要寻找答案，而是寻找如何进行的提示。我应该如何解决这个问题？
看看这里http://www.pressingquestion.com/3830657/Computing-Minimum-Cost-With-Using-Dynamic-Programming。这是一个和你非常相似的问题。该问题的解决方案表明您的问题是NP-Hard，而不是多项式。但是，如果您以这些目标在线而不是在线上方的方式稍微改变您的问题，那么您可以使用动态编程方法来解决它。链接中提供了详细信息。
如果您的问题没有改变，并且您仍然想要一个多项式解决方案，那么您可能需要假设传感器以稀疏的方式放置。在这种情况下，您可以使用分而治之的方法。沿线方向对所有传感器进行排序（假设线 L 为 x 轴，然后按 x 坐标对传感器进行排序），然后从中间开始划分。划分时，您需要推理那些 x 坐标离您非常仔细划分的点很近（不超过 1）的点。如果有太多点，算法将不是多项式的，这就是需要稀疏假设的原因。