一种用于k有限资源的贪心算法

Question

一种用于k有限资源的贪心算法

6

我正在学习贪婪算法，想知道一个不同情况的解决方案。

对于区间选择问题，我们希望选择的活动数量最多，且它们之间不会发生冲突，因此选择完成时间最早的工作是可行的。

另一个例子; 我们有n个工作需要完成，希望购买尽可能少的资源。在这种情况下，我们可以将所有工作按从左到右的顺序排列，当我们遇到新的起点时，我们增加一个计数器，当我们遇到终点时，我们减少计数器。所以从这个计数器获得的最大值将是我们需要购买的资源数量。

但是例如，如果我们有n个任务，但只有k个资源怎么办？如果我们无法支付更多的资源，那么应该采用什么贪心策略来删除最少的任务以满足要求？

此外，如果我写的最后一个问题有特定名称，我会很高兴听到这个名称。

- user973888

听起来可能是背包问题？我会研究一些类似模拟退火的算法。 - Mike Christensen

无需模拟退火算法，这个问题有一个简单的O(N lg N)确定性解决方案。请参见此相关问题，针对k=2情况进行了推广。 (k=1太简单了，不能推广到k=2) - xdavidliu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MAK · Accepted Answer

这看起来像是只有一个资源的版本的一般情况。

直观上，按结束时间对作业进行排序并按顺序逐个接受它们仍然是有意义的。现在，我们不再跟踪最后一个作业的结束时间，而是跟踪最后k个作业被分配到我们的资源的结束时间。对于每个作业，我们检查当前作业的开始时间是否大于我们任何一个资源中的最后一个作业。如果没有找到这样的资源，我们跳过该作业并继续向前移动。如果找到一个资源，我们将该作业分配给该资源并更新结束时间。如果有多个资源能够承担该作业，将其分配给最后结束时间的资源是有意义的。

我实际上没有这种贪心策略的证明，所以它可能是错误的。但我想不出改变选择可能使我们能够安排更多作业的情况。