Najmniejszy podzbiór tablicy, której suma jest nie mniejsza niż klucz

Question

Biorąc pod uwagę tablicę (pozwala założyć, że nieujemne liczby całkowite) musimy znaleźć najmniejszy podzbiór długości, tak aby suma elementów była nie mniejsza niż K. K to inna liczba całkowita podana jako wejście.

Czy możliwe jest rozwiązanie o złożoności czasowej O (n) [big oh of n]?

moje obecne myślenie jest następujące: możemy posortować tablicę w O (n * log n), a następnie powtórzyć sortowaną tablicę, zaczynając od największej liczby i utrzymując sumę roboczą, aż suma bieżąca stanie się> = K.

Jednak najgorszy przypadek to czas działania O (n * (log n + 1)).

Więc jeśli ktoś mógłby podzielić się idee robi to w czasie O (n), będę naprawdę wdzięczny ..

Uwaga: Elementy subarray nie trzeba być ciągłą sekwencję oryginalnej tablicy w tym kontekście

Answer 1

Istnieje algorytm liniowy czasu do znajdowania K największych liczb - http://en.wikipedia.org/wiki/Selection_algorithm. Oczywiście to, czego potrzebujesz, jest wystarczającą liczbą największych sum, by sumować się do co najmniej K.

W standardowym algorytmie wyboru bierzesz losowy pivot, a następnie sprawdzasz, ile liczb spada z każdej strony. Następnie akceptujesz lub odrzucasz połowę i kontynuujesz pracę nad drugą połową. Wystarczy spojrzeć na każdą liczbę w każdej połowie, po kolei - koszt każdego etapu obrotu jest liniowy, ale ilość danych rozpatrywanych na każdym etapie zmniejsza się wystarczająco szybko, aby całkowity koszt był nadal tylko liniowy.

Koszt etapu przestawnego będzie nadal liniowy, jeśli weźmie się sumę wszystkich liczb powyżej liczby przestawnej. Używając tego, możesz się dowiedzieć, czy przyjęcie wszystkich tych numerów, wraz z dowolnymi poprzednio wybranymi numerami, dałoby ci kolekcję liczb, które sumują się do co najmniej K. Jeśli tak, możesz porzucić inne liczby i użyć numerów powyżej osią obrotu dla następnego przejścia. Jeśli nie, możesz zaakceptować wszystkie liczby powyżej osi obrotu i użyć liczb pod osią obrotu dla następnego przejścia. Podobnie jak w przypadku algorytmu wyboru, sam pivot i wszelkie powiązania dają kilka specjalnych przypadków i możliwość wcześniejszego znalezienia dokładnej odpowiedzi.

(Tak myślę, że możesz zrobić to w (randomizowanym) czasie liniowym używając zmodyfikowanej wersji algorytmu selekcji, w którym patrzysz na sumę liczb powyżej osi obrotu, zamiast liczby liczb powyżej czopa.

Answer 2

To wydaje się być problemem dla programowania dynamicznego. Podczas budowania macierzy budujemy kolejną tablicę zawierającą sumę skumulowaną do każdego konkretnego indeksu. Więc każdy i w tej tablicy ma sumy od 1..i.

Teraz to łatwo zauważyć, że suma wartości dla indeksów p..q jest SUM(q) - SUM(p-1) (ze szczególnym przypadku, SUM(0) jest 0). Oczywiście używam tutaj indeksów 1-bazowych ... Ta operacja to O (1), więc teraz potrzebujesz tylko algorytmu O (n), aby znaleźć najlepszy.

Prostym rozwiązaniem jest śledzenie p i q i przechodzenie przez tablicę. Na początek rozwijasz się pod numerem q. Następnie zamawiasz p i wielokrotnie rozwiń q, jak gąsienica przeszukiwana przez twoją tablicę.

Aby rozwinąć q:

p <- 1 
q <- 1 

while SUM(q) - SUM(p-1) < K 
    q <- q + 1 
end while 

Teraz q jest w pozycji, w której suma subarray właśnie przekroczony (lub równy) K. Długość podprzestrzeni to q - p + 1.

Po pętli q sprawdza się, czy długość podprzestrzeni jest mniejsza od aktualnej. Następnie należy wykonać krok o krok p (tak, aby nie przypadkowo pominąć optymalnego rozwiązania) i przejść ponownie.

Nie musisz tworzyć macierzy SUM ... Możesz po prostu zbudować sumę podprzestrzeni w trakcie pracy ... Musisz wrócić do korzystania z "prawdziwej" p zamiast tej, która była tuż przed .

subsum <- VAL(1) 
p <- 1 
q <- 1 

while q <= N 
    -- Expand 
    while q < N and subsum < K 
     q <- q + 1 
     subsum <- subsum + VAL(q) 
    end while 

    -- Check the length against our current best 
    len <- q - p + 1 
    if len < bestlen 
     ... 
    end if 

    -- Contract 
    subsum <- subsum - VAL(p) 
    p <- p + 1 
end while 

Uwagi:

j_random_hacker powiedział: to pomóc wyjaśnić, dlaczego dopuszczalne jest zbadanie tylko O ​​(N) różne subarrays że ten algorytm przeprowadza oględziny, zamiast wszystkich O (n^2) różnych możliwych subarrays

dynamiczny filozofii programowania:

1. nie podążaj za ścieżkami rozwiązania, które doprowadzą do nieoptymalnego wyniku; i
2. wykorzystać wiedzę z wcześniejszych rozwiązań do obliczenia nowego rozwiązania.

W tym przypadku jednego kandydata roztworu (około (p,q) tak, że p <= q) oblicza się poprzez sumowanie elementów. Ponieważ te elementy są liczbami całkowitymi dodatnimi, wiemy, że dla dowolnego kandydata na rozwiązanie (p,q), kandydat na rozwiązanie (p,q+1) będzie większy.

A więc wiemy, że jeśli (p,q) jest rozwiązaniem minimalnym, to nie jest to (p,q+1). Kończymy nasze poszukiwania, gdy tylko mamy kandydata, i sprawdzamy, czy ten kandydat jest lepszy niż jakikolwiek, który widzieliśmy do tej pory. Oznacza to, że dla każdego p musimy przetestować tylko jednego kandydata. To prowadzi do tego, że zarówno p, jak i q ciągle się zwiększa, a zatem wyszukiwanie jest liniowe.

Inna część tego (korzystanie z wcześniejszych rozwiązań) pochodzi od rozpoznania, że ​​sum(p,q+1) = sum(p,q) + X(q+1) i podobnie sum(p+1,q) = sum(p,q) - X(p). Dlatego nie musimy sumować wszystkich elementów między p i q na każdym kroku. Musimy tylko dodać lub odjąć jedną wartość za każdym razem, gdy przesuwamy jeden ze wskaźników wyszukiwania.

Nadzieję, że pomaga.

Answer 3

Oto rozwiązanie, które powinno być wystarczająco szybki. Zgaduję, że to prawie liniowy.

def solve(A, k): 
    assert sum(A) >= k 
    max_ = max(A) 
    min_ = min(A) 
    n = len(A) 
    if sum(A) - min_ < k: 
     return A 
    bucket_size = (max_ - min_)/n + 1 
    buckets = [] 
    for i in range(n): 
     buckets.append([]) 
    for item in A: 
     bucket = (item - min_)/bucket_size 
     buckets[bucket].append(item) 

    solution = [] 

    while True: 
     bucket = buckets.pop() #the last bucket 
     sum_ = sum(bucket) 
     if sum_ >= k: 
      #don't need everything from this bucket 
      return solution + solve(bucket, k) 
     else: 
      k -= sum_ 
      solution += bucket 

print solve([5,2,7,52,30,12,18], 100) 
"[52, 30, 18]" 

Answer 4

wierzę, że „sub array” termin oznacza ciągłą część tablicy (like here inny problem jako przykład)

Tak więc istnieje prosty algorytm O (n) do znalezienia subaraku o minimalnej długości:

Ustaw dwa indeksy (lewy, prawy) do pierwszego elementu i przenieś je do końca tablicy. Sprawdź sumę tych indeksów, przesuń wskaźnik w prawo, jeśli suma jest za mała (lub wskaźniki są równe), przesuń w lewo, jeśli suma jest duża

Answer 5

PO wyjaśnił w swoich odpowiedziach na uwagi, że problemem jest znalezienie podzbiór, niekoniecznie sekwencja ciągła (termin "subarray" był wprawdzie zły). Następnie, uważam, że metoda wskazana przez mcdowella jest poprawna i obejmuje następujące kroki:

Zaczynając od N elementów, znajdź element MEDIAN (tj. (N/2) -th element wyobrażający posortowaną tablicę, którą ty nie mają i nie konstruują). Osiąga się to za pomocą algorytmu "Median of Medians", udowodnionego, że jest to O (n), zobacz wiki ref podany i powtórzony tutaj: Selection algorithm, see section on the Median of Median algorithm

Posiadanie elementu medianowego: skanowanie liniowo całego zestawu i partycji w " poniżej "i" powyżej ", w międzyczasie sumując, licząc i robiąc to, co chcesz śledzić, dla każdej z" połówek ". Ten etap to (także) O (N).

Po zakończeniu skanowania, jeśli suma "górnej połowy" znajduje się powyżej celu (K), zapomina się o dolnej połowie i powtórzyć procedurę dla górnej połowy, której rozmiar jest (z grubsza) N/2 . Jeśli, z drugiej strony, suma "górna połowa" jest mniejsza niż K, to należy dodać górną połowę do końcowego wyniku, odjąć jej sumę od K i powtórzyć procedurę z dolną połówką:

Łącznie , przetwarzasz zbiory wielkości N, N/2, N/4, N/8 etcetera, każdy w O (M) w odniesieniu do ich odpowiednich rozmiarów M, a więc cały materiał jest również liniowy w N, ponieważ N + N/2 + N/4 + N/8 ... pozostaje poniżej 2N.

Answer 6

subarray musi sąsiadować z definicji podanej tablicy.

użyciu 2 wskaźniki (początek, koniec). inicjować je do początek tablicy Śledź bieżącą sumę pomiędzy (początek, koniec), d przesuń od końca do prawej pojedynczo. Za każdym razem, gdy poruszasz wskaźnikiem końcowym, suma = suma + tablica [koniec].

A gdy suma = = cel, zacznij przesuwać start w prawo i zachowaj sumę śledzenia jako suma = suma - tablica [start].

Podczas poruszania się od początku w prawo, sprawdzaj, czy suma nie jest mniejsza od wartości docelowej. Musimy również śledzić długość, wykonując length = end - start + 1, a także minLength = min (minLength, length).

Teraz, gdy przesunęliśmy oba wskaźniki tak, jak to możliwe, wystarczy zwrócić minLength.

Generalnie chodzi o to, aby najpierw znaleźć "okno", które spełnia warunek (suma = = cel), a następnie przesuwać okno do prawego po jednym elemencie naraz i utrzymywać minimalny rozmiar okna za każdym razem, gdy przesuniemy okno.