algorithm - 什么类别的算法可以用来解决这个问题？

Question

编辑:只是为了确保有人不会在这个问题上崩溃...我不是在寻找最佳算法。一些有意义的启发式方法很好。

我之前曾尝试制定此问题，但意识到我在这方面做得并不好，因此我删除了该问题。我又一次提出了我的问题。请随时提供任何可以帮助我改进这一点的建设性批评。

输入:

• N个人
• 我可以发布的 k 个公告
• 可以听到我的声音的距离(比如 5 米)，即我可以根据这 5 米内的人数决定是否宣布

目标:

• 最大化听到我的 k 个公告的总人数，并(可选)最小化我可以完成所有 k 个公告的时间

约束:

• 一旦有人听到我的通知，他就会从总数中删除，即如果他听到了我的第一次通知，即使他听到了我的第二次通知，我也不算他
• 我可以在附近看到同一个人以及同一群人

示例:让我们考虑从 1 到 10 编号的 10 个人以及以下到达模式:

• 时间段 1:1( yield = 1)
• 时间段 2:2 3 4 5( yield = 4)
• 时间段 3:5 6 7 8(如果先前没有在时间段 2 中发布公告，则 yield = 4；如果在时间段 2 中发布公告，则 yield = 3)
• 时间段 4:9 10( yield = 2)

我要发布 2 个公告。现在，如果我是神谕，我会选择时间段 2 和时间段 3，因为那时会有 7 个人听到(因为 5 人已经在时间段 2 听到我的公告，我不再考虑他了)。我正在寻找一种在线算法，它可以帮助我就是否发布公告以及是否发布公告基于哪些因素做出这些决定。有没有人对可以使用什么算法来解决这个问题或这个问题的更简单版本有任何想法？

Answer 1

应该有一种方法依赖于最大流算法。本质上，您正在尝试从开始-> 结束推送最大数量的消息。虽然它是多维的，但你可以有一个 super 汇，它连接到每个 t 值，然后让每个 t 值连接到你此时可以接触到的人，然后有一个 super 汇。这样，您只需计算一个最大流量(附加限制不超过 k 声，这应该可以通过一些动态规划来解决)。这是一种非常肮脏的解决方法，但它应该可以确定地完成工作，而无需使用启发式方法。