我正在学习贪婪算法,想知道一个不同情况的解决方案。
对于区间选择问题,我们希望选择的活动数量最多,且它们之间不会发生冲突,因此选择完成时间最早的工作是可行的。
另一个例子; 我们有n个工作需要完成,希望购买尽可能少的资源。在这种情况下,我们可以将所有工作按从左到右的顺序排列,当我们遇到新的起点时,我们增加一个计数器,当我们遇到终点时,我们减少计数器。所以从这个计数器获得的最大值将是我们需要购买的资源数量。
但是例如,如果我们有n个任务,但只有k个资源怎么办? 如果我们无法支付更多的资源,那么应该采用什么贪心策略来删除最少的任务以满足要求?
此外,如果我写的最后一个问题有特定名称,我会很高兴听到这个名称。
对于区间选择问题,我们希望选择的活动数量最多,且它们之间不会发生冲突,因此选择完成时间最早的工作是可行的。
另一个例子; 我们有n个工作需要完成,希望购买尽可能少的资源。在这种情况下,我们可以将所有工作按从左到右的顺序排列,当我们遇到新的起点时,我们增加一个计数器,当我们遇到终点时,我们减少计数器。所以从这个计数器获得的最大值将是我们需要购买的资源数量。
但是例如,如果我们有n个任务,但只有k个资源怎么办? 如果我们无法支付更多的资源,那么应该采用什么贪心策略来删除最少的任务以满足要求?
此外,如果我写的最后一个问题有特定名称,我会很高兴听到这个名称。