是否有可能解决此问题的贪心算法。我已经为它制定了一个 DP 算法，但我不确定它的贪心算法。请解释是否存在贪心算法。
对于那些不熟悉该问题的人：
从 a1 到 a 有“n”个活动。每个活动 ai 都有一个相关的开始时间 si 和一个结束时间 fi 即 [si,fi)。每个活动 ai 也有一个与之关联的值 vi。没有两个活动可以同时发生。任务是选择相互兼容的活动，以使总价值最大化，即所有计划活动的总和。相互兼容意味着它们的运行时间不重叠。
问问题
1861 次
1 回答
0
为了找到一个问题的贪婪解决方案，我们必须找到它背后的直觉。这个问题看起来类似于 CLRS ( section 16.1) 文本中的活动选择问题。在那个问题中，我们要找到一个最大尺寸的集合，其中每个活动都相互兼容。但是这个问题还有另一个目标，它希望我们找到一个最大化覆盖或资源使用的集合。
在我看来，解决这个问题的方法是首先根据活动的开始时间对所有活动进行排序。它背后的直觉是我们希望尽可能快地使用时间/价值/资源，而不是浪费任何东西。然后，我们开始挑选最长的活动，并检查它是否与迄今为止选择的其他活动兼容。而你继续拾取到最后。如果你把它应用到书中的例子中，它会给你一个带有活动的集合{3, 7, 11}。
它可能不适用于所有活动集。例如，一组两个活动：activity(1) = <0, 2>和activity(2) = <1, 5>。
如您所见，这个想法在这种情况下不起作用。所以你必须再次应用它，但从右到左。（根据完成时间对它们进行排序，然后选择最先完成且持续时间更长的那些！）最后，您将选择覆盖率最高的集合！
我可能还没有产生最好的结果。如果我们添加另一个活动activity(3)=<4, 6>，这些方法不是答案。因此，根据活动的长度按降序对活动进行排序可能是答案。
最后，这三种方法中的一种应该给出答案。
于 2016-02-13T20:56:04.857 回答