Największa suma podzielna przez n

Zadałem to pytanie na StackOverflow , ale myślę, że tutaj jest bardziej odpowiednie miejsce.

Jest to problem od kursu Wprowadzenie do algorytmów :

Musisz tablicę $a$ z liczb całkowitych dodatnich (tablica nie muszą być sortowane lub elementów unikalnych). Zaproponuj algorytm , aby znaleźć największą sumę elementów, która jest podzielna przez . $n$ $O(n)$ $n$

Przykład: . Odpowiedź to (z elementami ) $a = [6, 1, 13, 4, 9, 8, 25], n = 7$ $56$ $6, 13, 4, 8, 25$

Stosunkowo dynamicznie jest go znaleźć w przy użyciu programowania dynamicznego i przechowując największą sumę z resztą . $O(n^2)$ $0, 1, 2,..., n - 1$

Ponadto, jeśli ograniczenia uwagę na ciągłej sekwencji elementów, łatwo znaleźć optymalną takiej sekwencji w czasie przechowywania cząstkowych sumy modulo niech , dla każdej reszty pamiętaj największy indeks taki, że , a następnie dla każdego rozważasz gdzie jest indeksem odpowiadającym . $O(n)$ $n$ $S[i]=a[0]+a[1]+\dots + a[i]$ $r$ $j$ $S[j] \equiv r \pmod{n}$ $i$ $S[j]-S[i]$ $j$ $r=S[i] \bmod n$

Ale czy istnieje rozwiązanie czasu $O(n)$ w przypadku ogólnym? Wszelkie sugestie będą mile widziane! Myślę, że ma to coś wspólnego z algebrą liniową, ale nie jestem pewien, co dokładnie.

Alternatywnie, czy można to zrobić w czasie $O(n \log n)$ ?

algorithms optimization dynamic-programming arrays delta-terminator
źródło

1. Opublikowałeś dokładnie to samo pytanie na temat Przepełnienia stosu. Proszę nie pisać to samo pytanie na wielu stronach . Nie chcemy, aby wiele kopii krążyło po wielu witrynach SE. Jeśli nie otrzymałeś akceptowalnej odpowiedzi, możesz oflagować swoje pytanie w celu migracji do innej witryny, ale nie publikuj tego samego w innym miejscu. 2. Czy możesz podać odniesienie / cytat / link do podręcznika lub kursu, w którym się pojawił? Czy jesteś pewien, że istnieje rozwiązanie czasu

O (n)

$O(n)$ ?

Czy wyzwanie na twoim uniwersytecie jest nadal otwarte? Byłoby naprawdę pomocne zobaczyć link do kursu, dokładne pytanie, a jeśli tak naprawdę jest a ludzie, którzy go przygotowali, wyjaśnią / opublikują swoją odpowiedź, byłoby wspaniale.

O (n)

$O(n)$

Zły

Stosunkowo łatwo jest go znaleźć w O (n2) O (n2) przy użyciu programowania dynamicznego i przechowywania największej sumy z resztą 0,1,2, ..., n − 10,1,2, ..., n − 1. Czy mógłbyś to trochę rozwinąć? Rozumiem, jak byłoby to n-kwadrat, jeśli weźmiemy pod uwagę tylko elementy przyległe, ale także w przypadku elementów niesąsiadujących, czy nie byłoby to wykładnicze w porządku?

Nithish Inpursuit Ofhappiness

Odpowiedzi:

Oto kilka przypadkowych pomysłów:

Algorytm programowania dynamicznego można przerzucić, aby wyszukać najmniejszą sumę zamiast największej. Po prostu kończysz na szukaniu sumy zgodnej z resztą sumy całej tablicy, zamiast jednej przystawki do zera. Jeśli przetwarzamy elementy w kolejności rosnącej, czasami pozwala to na zakończenie algorytmu dynamicznego przed przetworzeniem całej tablicy.

Koszt wyniósłby , gdybyśmy przetworzyli elementów. W tym algorytmie nie ma dolnej granicy , ponieważ nie musimy sortować wszystkich elementów. Zajmuje tylko czas, aby uzyskać najmniejszych elementów. $O(n k)$ $k$ $\Omega(n \log n)$ $O(n \log k)$ $k$
Jeśli zależy nam na zbiorze o dużych rozmiarach, zamiast zestawu o największej sumie, możemy być w stanie użyć mnożenia wielomianowego opartego na szybkiej transformacie Fouriera, aby rozwiązać problem w czas. Podobne do tego, co zrobiono w 3SUM, gdy zakres domen jest ograniczony. (Uwaga: użyj powtarzania kwadratu, aby przeprowadzić wyszukiwanie binarne, w przeciwnym razie otrzymasz gdzie jest liczbą pominiętych elementów.) $O(n (\log n)^2 (\log \log n))$ $O(n k (\log n) (\log \log n))$ $k$
Gdy jest złożone, a prawie wszystkie pozostałe są wielokrotnością jednego z czynników , można zaoszczędzić znaczny czas, skupiając się na pozostałych, które nie są wielokrotnością tego czynnika. $n$ $n$
Gdy reszta rjest bardzo powszechna lub pozostało tylko kilka, śledzenie „następnego otwartego slotu, jeśli zaczniesz od tego miejsca i będziesz przechodzić dalej r”, może zaoszczędzić wiele skanowania w poszukiwaniu skoków w otwarte miejsca czas.
Możesz ogolić współczynnik logarytmiczny, śledząc jedynie osiągalność i używając masek bitowych (w odwróconym algorytmie dynamicznym), a następnie cofając się po osiągnięciu pozostałej wartości docelowej.
Algorytm programowania dynamicznego jest bardzo podatny na równoległe działanie. Z procesorem dla każdego gniazda bufora możesz przejść do . Alternatywnie, używając szerokości oraz dzielenia i zdobywania agregacji zamiast agregacji iteracyjnej, koszt głębokości obwodu może spaść aż do . $O(n)$ $O(n^2)$ $O(\log^2 n)$
(Meta) Podejrzewam, że podany przez ciebie problem dotyczy ciągłych sum. Jeśli powiązałeś się z rzeczywistym problemem, łatwo byłoby to zweryfikować. W przeciwnym razie jestem bardzo zaskoczony, jak trudny jest ten problem, biorąc pod uwagę, że został on przypisany w kursie o nazwie „Wprowadzenie do algorytmów”. Ale może omówiłeś w klasie sztuczkę, która czyni ją trywialną.

Craig Gidney
źródło

Dla punktu pierwszego. Nie jest to zapisane w specyfikacji problemu, więc nie możesz tego założyć. Problemem nie jest również to, że nie możesz modyfikować tablicy ani tworzyć nowych, możesz to zrobić. Jedyne, co musisz zrobić, to znaleźć zsumowane liczby, aby uzyskać największą sumę, która jest podzielna przez w złożoności czasowej (zwykle przyjmuje się tylko złożoność czasową).

n

$n$

O (n)

$O(n)$

nbro

@EvilJS Podzbiór z największą sumą z resztą 0 jest równy pełnemu zestawowi po usunięciu podzestawu z najmniejszą sumą z resztą przystającą do sumy pełnego zestawu. Szukanie najmniejszej sumy przystającej do jest wygodniejsze niż szukanie największej sumy przystającej do ponieważ pozwala ona na zakończenie, gdy tylko znajdziesz rozwiązanie (przy przetwarzaniu elementów w kolejności rosnącej), zamiast konieczności kontynuowania.

r_{1}

$r_1$

r_{2}

$r_2$

Craig Gidney

-1

Mój proponowany algorytm wygląda następująco:

Suma dzieli się przez n, jeśli dodasz tylko sumy będące wielokrotnościami n.

Zanim zaczniesz, tworzysz mapę z int jako kluczem i listą indeksów jako wartością. Tworzysz także listę wyników zawierającą indeksy.

Następnie zapętlasz tablicę i dodajesz każdy indeks, którego mod n wynosi zero, do listy wyników. Dla każdego innego indeksu wykonaj następujące czynności:

Odejmujesz wartość mod n tego indeksu od n. Ten wynik jest kluczem do twojego hashapa, który przechowuje indeksy dla elementów o wymaganej wartości. Teraz dodajesz ten indeks do listy w haszapie i idziesz dalej.

Po zakończeniu zapętlania tablicy macierz oblicza dane wyjściowe. Robisz to, sortując każdą listę w haszapie zgodnie z wartością wskazywaną przez indeks. Teraz weźmiesz pod uwagę każdą parę w haszpie sumującą się do n. Więc jeśli n = 7, przeszukujesz hashap dla 3 i 4. Jeśli masz wpis w obu, bierzesz dwie największe wartości, usuwasz je z ich list i dodajesz do swojej listy wyników.

Ostatnia rekomendacja: nadal nie testowałem algorytmu, napisz test z nim za pomocą algorytmu brutalnej siły.

Tobias Würfl
źródło

Chciwy, liniowy, nie działa. Rozważasz tylko elementy, które są podzielne przez n, i pary podzielne przez n, a co z potrójnymi i więcej? Nie gwarantuje maksymalnej sumy podzbioru w przypadku trywialnym. [2, 1, 8] -> maksymalna suma wynosi 9, ale algorytm zwraca 3.

Zły

n^{2}

$n^2$

Dzięki za zwrócenie mi uwagi na ten błąd. Moim pomysłem na ulepszenie byłoby utworzenie mapy stosów list, która jest uporządkowana przez zwiększenie wartości i zaczyna się gromadzić dopiero po ukończeniu przejścia przez tablicę.

Tobias Würfl,

Masz na myśli tablicę tablic, które zostaną posortowane, a „hashmap” to% n? Nadal musisz je posortować, a jeśli masz je posortowane, przyjmowanie wartości minimalnej / maksymalnej jest w porządku, ale nadal istnieje nieunikniona część faktycznego wyboru podzbioru, co w najgorszym przypadku nie przynosi korzyści. W każdym razie, jeśli masz jakieś ulepszenia, może mógłbyś edytować post?

Zły

Tak, to był dość szybki pomysł ze stosami. W rzeczywistości potrzebujesz tylko list w haszapie, który sortujesz. Nie byłem pewien, czy edytowanie mojej pierwszej odpowiedzi jest grzeczne. W końcu popełniłem błąd przy pierwszej próbie.

Tobias Würfl,

-2

użyj tej metody DP z ( /programming/4487438/maximum-sum-of-non-consecutive-elements?rq=1 ):

Biorąc pod uwagę tablicę A [0..n], niech M (i) będzie optymalnym rozwiązaniem wykorzystującym elementy o indeksach 0..i. Następnie M (-1) = 0 (użyte w nawrocie), M (0) = A [0], a M (i) = max (M (i - 1), M (i - 2) + A [i ]) dla i = 1, ..., n. M (n) to rozwiązanie, którego chcemy. To jest O (n) . Możesz użyć innej tablicy do zapisania wyboru dokonanego dla każdego podproblemu, aby odzyskać wybrane elementy.

Zmień rekurencję na M (i) = max (M (i - 1), M (i - 2) + A [i]) tak, że jest przechowywana tylko wtedy, gdy jest podzielna przez N

Główka szpilki
źródło

To nie działa - pozwolę ci zrozumieć, dlaczego. (Wskazówka: spróbuj uruchomić go na stałej tablicy 1.) Ponadto w tym problemie zezwalamy na kolejne elementy.

Yuval Filmus

To bardzo dobre rozwiązanie, całkowicie innego (i znacznie łatwiejszego) problemu.

Zły