Jak wybrać najmniejszą liczbę odważników, aby uzyskać całkowitą masę w czasie O (n)?

Question

Jeśli są n nieposortowane wagi i muszę znaleźć najmniejszą liczbę odważników, aby uzyskać przynajmniej wagę W. Jak je znaleźć w O(n)?

Answer 1

Ten problem ma wiele metod rozwiązania:

Metoda 1 - Sortowanie - O (nlogn)
Myślę, że najbardziej trywialne jeden byłoby uporządkować w kolejności malejącej, a następnie podjąć pierwsze elementy K które dają sumę co najmniej W. Złożoność czasu będzie wynosiła O(nlogn).

Metoda 2 - max stosu - O (n + klogn)
Innym sposobem jest użycie max sterty. Tworzenie sterty zajmie O(n), a następnie wyodrębnianie elementów, aż uzyskamy całkowitą sumę co najmniej W. Każda ekstrakcja zajmie O(logn), więc całkowita złożoność czasu będzie wynosić O(klogn), gdzie k jest liczbą elementów, które musieliśmy wyodrębnić ze sterty .

Metoda 3 - Korzystanie Min Heap - O (nlogk)
Dodanie tej metody, która JimMischel sugerowane w komentarzach poniżej.
Tworzenie minimalnej sterty z pierwszymi elementami k na liście, która wynosi co najmniej W. Następnie wykonaj iterację nad pozostałymi elementami i jeśli jest większa niż minimalna (stertowanie), wymień między nimi.
W tym momencie może być tak, że mamy więcej elementów tego, co faktycznie potrzebujemy, aby uzyskać W, więc wyodrębnimy minimalne wartości, dopóki nie osiągniemy limitu. W praktyce, w zależności od relacji pomiędzy

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() 

Metoda ta może być nawet szybciej w praktyce, w zależności od relacji pomiędzy k i n. Zobacz when theory meets practice.

Metoda 4 - O (n)
Najlepszy sposób może myślę zostanie przy użyciu pewnego rodzaju quickselect zachowując jednocześnie całkowitej wagi i zawsze przegród z medianą jako przegub.

Najpierw zdefiniować kilka rzeczy:

sum(A) - łączna suma wszystkich elementów w tablicy A.
num(A) - Liczba elementów w tablicy A.
med(A) - Mediana tablicy 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) 

Wywołanie tej metody przez find_min_set(A,W,0).

Runtime Złożoność:

• Znalezienie mediana O(n).
• Partycjonowanie to O(n).
• Każde wywołanie rekurencyjne zajmuje połowę rozmiaru tablicy.
• Podsumowując, otrzymujemy następujący stosunek: T(n) = T(n/2) + O(n), który jest taki sam jak średni przypadek quickselect = O(n).

Uwaga: Gdy wszystkie wartości są unikatowe zarówno najgorszy przypadek i średnia złożoność jest rzeczywiście O(n). Z możliwymi zduplikowanymi wartościami, średnia złożoność nadal wynosi O(n), ale najgorszy przypadek to O(nlogn) przy użyciu metody wybierania liczby przestawnej za pomocą metody Median of medians.