找到所需的最小元素数，以使它们的总和等于或超过S [英] Find the minimum number of elements required so that their sum equals or exceeds S

问题描述

我知道可以通过对数组进行排序并取更大的数字直到满足所需条件来完成。至少需要nlog（n）的排序时间。

I know this can be done by sorting the array and taking the larger numbers until the required condition is met. That would take at least nlog(n) sorting time.

与 nlog（n）相比有什么改进吗？

Is there any improvement over nlog(n).

我们可以假设所有数字都是正数。

We can assume all numbers are positive.

推荐答案

O（n + size（最小子集）* log（n））的算法。如果最小子集远小于数组，则将为 O（n）。

Here is an algorithm that is O(n + size(smallest subset) * log(n)). If the smallest subset is much smaller than the array, this will be O(n).

读取 http://en.wikipedia.org/wiki/Heap_%28data_structure%29 该算法的描述不清楚（细节很浅，但是细节都在那里）。

Read http://en.wikipedia.org/wiki/Heap_%28data_structure%29 if my description of the algorithm is unclear (it is light on details, but the details are all there).

1. 将数组变成排列的堆这样最大的元素在时间 O（n）可用。


2. 反复从堆中提取最大的元素，直到它们的和为足够大。这需要 O（大小（最小子集）* log（n））。

1. Turn the array into a heap arranged such that the biggest element is available in time O(n).
2. Repeatedly extract the biggest element from the heap until their sum is large enough. This takes O(size(smallest subset) * log(n)).

这几乎可以肯定是他们所希望的答案，尽管没有得到应该不会破坏交易。

This is almost certainly the answer they were hoping for, though not getting it shouldn't be a deal breaker.

编辑：是另一个变体，通常变快，但变慢。

Here is another variant that is often faster, but can be slower.

Walk through elements, until the sum of the first few exceeds S.  Store current_sum.
Copy those elements into an array.
Heapify that array such that the minimum is easy to find, remember the minimum.
For each remaining element in the main array:
    if min(in our heap) < element:
        insert element into heap
        increase current_sum by element
        while S + min(in our heap) < current_sum:
            current_sum -= min(in our heap)
            remove min from heap

如果我们在不操纵堆的情况下拒绝了大多数数组，则速度可能是前一个解决方案的两倍。但是也可能会变慢，例如当数组中的最后一个元素碰巧大于S时。

If we get to reject most of the array without manipulating our heap, this can be up to twice as fast as the previous solution. But it is also possible to be slower, such as when the last element in the array happens to be bigger than S.

这篇关于找到所需的最小元素数，以使它们的总和等于或超过S的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！