How to choose the least number of weights to get a total weight in O(n) time

Question

If there are n unsorted weights and I need to find the least number of weights to get at least weight W. How do I find them in O(n)?

Answer 1

This problem has many solution methods:

Method 1 - Sorting - O(nlogn)
I guess that the most trivial one would be to sort in descending order and then to take the first K elements that give a sum of at least W. The time complexity will be though O(nlogn).

Method 2 - Max Heap - O(n + klogn)
Another method would be to use a max heap. Creating the heap will take O(n) and then extracting elements until we got to a total sum of at least W. Each extraction will take O(logn) so the total time complexity will be O(klogn) where k is the number of elements we had to extract from the heap.

Method 3 - Using Min Heap - O(nlogk)
Adding this method that JimMischel suggested in the comments below.
Creating a min heap with the first k elements in the list that sums to at least W. Then, iterate over the remaining elements and if it's greater than the minimum (heap top) replace between them.
At this point, it might be that we have more elements of what we actually need to get to W, so we will just extract the minimums until we reach our limit. In practice, depending on the relation between

find_min_set(A,W)
    currentW = 0
    heap H //Create empty heap

    for each Elem in A
        if (currentW < W)
            H.add(Elem)
            currentW += Elem
        else if (Elem > H.top())
            currentW += (Elem-H.top())
            H.pop()
            H.add(Elem)

    while (currentW-H.top() > W)
        currentW -= H.top()
        H.pop()

This method might be even faster in practice, depending on the relation between k and n. See when theory meets practice.

Method 4 - O(n)
The best method I could think of will be using some kind of quickselect while keeping track of the total weight and always partitioning with the median as a pivot.

First, let's define few things:

sum(A) - The total sum of all elements in array A.
num(A) - The number of elements in array A.
med(A) - The median of the array A.

find_min_set(A,W,T)
    //partition A
    //L contains all the elements of A that are less than med(A)
    //R contains all the elements of A that are greater or equal to med(A)
    L, R = partition(A,med(A))
    if (sum(R)==W)
        return T+num(R)
    if (sum(R) > W)
        return find_min_set(R,W,T)
    if (sum(R) < W)
        return find_min_set(L,W-sum(R),num(R)+T)

Calling this method by find_min_set(A,W,0).

Runtime Complexity:

• Finding median is O(n).
• Partitioning is O(n).
• Each recursive call is taking half of the size of the array.
• Summing it all up we get a follow relation: T(n) = T(n/2) + O(n) which is same as the average case of quickselect = O(n).

Note: When all values are unique both worst-case and average complexity is indeed O(n). With possible duplicates values, the average complexity is still O(n) but the worst case is O(nlogn) with using Median of medians method for selecting the pivot.