Ich habe diese Frage auf StackOverflow gestellt , aber ich denke, hier ist ein geeigneterer Ort.
Dies ist ein Problem aus dem Kurs Einführung in Algorithmen :
Sie haben ein Array mit positiven ganzen Zahlen (das Array muss nicht sortiert oder die Elemente eindeutig sein). Schlagen Sie einen -Algorithmus vor, um die größte durch teilbare Summe von Elementen zu finden .
Beispiel: . Die Antwort ist (mit Elementen )
Mit dynamischer Programmierung und Speichern der größten Summe mit dem Rest 0 , 1 , 2 , ist es relativ einfach, sie in zu finden . . . , N - 1 .
Wenn wir die Aufmerksamkeit auf eine zusammenhängende Folge von Elementen beschränken, ist es auch einfach, die optimale Folge in Zeit zu finden, indem Teilsummen modulo gespeichert werden : sei , für jeden Rest merken Sie sich den größten Index so dass , und dann für jedes Sie S [j] -S [i] wobei ji S [ j ] - S [ i ] jist der Index, der .
Aber gibt es eine -Zeitlösung für den allgemeinen Fall? Vorschläge werden geschätzt! Ich denke, dies hat etwas mit linearer Algebra zu tun, aber ich bin mir nicht sicher, was genau.
Alternativ kann dies in Zeit erfolgen?
quelle
Antworten:
Hier sind ein paar zufällige Ideen:
Der Algorithmus zur dynamischen Programmierung kann umgedreht werden, um nach einer kleinsten Summe anstelle einer größten Summe zu suchen. Am Ende suchen Sie nur nach einer Summe, die zum Rest der Summe des gesamten Arrays kongruent ist, anstatt einer, die kongruent zu Null ist. Wenn wir die Elemente in aufsteigender Reihenfolge verarbeiten, kann der dynamische Algorithmus manchmal beendet werden, bevor das gesamte Array verarbeitet wird.
Die Kosten wären wenn wir Elemente verarbeiten würden . Es gibt keine Untergrenze von für diesen Algorithmus, da wir nicht alle Elemente sortieren müssen. Es dauert nur , um die kleinsten Elemente zu erhalten.k Ω ( n log n ) O ( n log k ) kO(nk) k Ω(nlogn) O(nlogk) k
Wenn wir uns um die Menge mit der größten Größe kümmern würden, könnten wir anstelle der Menge mit der größten Summe eine auf einer schnellen Fouriertransformation basierende Polynommultiplikation verwenden, um das Problem in zu lösen Zeit. Ähnlich wie in 3SUM, wenn der Domänenbereich begrenzt ist. (Hinweis: Verwenden Sie wiederholtes Quadrieren, um eine binäre Suche durchzuführen. Andernfalls erhalten Sie wobei die Anzahl der ausgelassenen Elemente ist.)O ( n k ( log n ) ( log log n ) )O(n(logn)2(loglogn)) O(nk(logn)(loglogn)) k
Wenn ist und fast alle Reste ein Vielfaches eines der Faktoren sind, kann durch die Konzentration auf die Reste, die kein Vielfaches dieses Faktors sind, erhebliche Zeitersparnis erzielt werden.nn n
Wenn ein Rest
r
sehr häufig ist oder nur wenige Reste vorhanden sind, kann das Verfolgen derr
Informationen über den nächsten offenen Steckplatz, wenn Sie von hier aus beginnen und weiter voranschreiten , eine Menge von Suchanfragen nach offenen Stellen ersparen Zeit.Sie können einen Protokollfaktor rasieren, indem Sie nur die Erreichbarkeit nachverfolgen und Bitmasken verwenden (im umgedrehten dynamischen Algorithmus) und dann zurückverfolgen, sobald Sie den Zielrest erreicht haben.
Der dynamische Programmieralgorithmus kann sehr leicht parallel ausgeführt werden. Mit einem Prozessor für jeden Pufferslot können Sie zu . Alternativ können die Schaltkreistiefenkosten durch Verwendung der Breite und durch Teilen und Erobern der Aggregation anstelle der iterativen Aggregation bis hinunter zu .O ( n 2 ) O ( log 2 n )O(n) O(n2) O(log2n)
(Meta) Ich vermute sehr, dass es sich bei dem Problem, das Sie erhalten haben, um zusammenhängende Summen handelt. Wenn Sie auf das eigentliche Problem verweisen, ist dies leicht zu überprüfen. Ansonsten wundert es mich sehr, wie schwierig dieses Problem ist, da es in einem Kurs mit dem Titel "Einführung in Algorithmen" behandelt wurde. Aber vielleicht haben Sie im Unterricht einen Trick verdeckt, der es trivial macht.
quelle
Mein vorgeschlagener Algorithmus lautet wie folgt:
Eine Summe ist durch n teilbar, wenn Sie nur Summanden addieren, die Vielfache von n sind.
Bevor Sie beginnen, erstellen Sie eine Hashmap mit einem int als Schlüssel und einer Liste von Indizes als Wert. Sie erstellen auch eine Ergebnisliste mit Indizes.
Anschließend durchlaufen Sie das Array und fügen Ihrer Ergebnisliste jeden Index hinzu, dessen Mod n Null ist. Für jeden anderen Index gehen Sie wie folgt vor:
Sie subtrahieren den Wert mod n dieses Index von n. Dieses Ergebnis ist der Schlüssel für Ihre Hashmap, die Indizes für Elemente mit dem erforderlichen Wert speichert. Jetzt fügen Sie diesen Index der Liste in der Hashmap hinzu und fahren fort.
Nachdem Sie das Array durchlaufen haben, berechnen Sie die Ausgabe. Dazu sortieren Sie jede Liste in der Hashmap nach dem Wert, auf den der Index zeigt. Nun betrachten Sie jedes Paar in der Hashmap, das sich zu n summiert. Wenn also n = 7 ist, durchsuchen Sie die Hashmap nach 3 und 4. Wenn Sie in beiden einen Eintrag erhalten haben, nehmen Sie die beiden größten Werte, entfernen Sie sie aus ihren Listen und fügen Sie sie Ihrer Ergebnisliste hinzu.
Letzte Empfehlung: habe den Algorithmus noch nicht getestet, schreibe einen Testfall mit einem Brute-Force-Algorithmus dagegen.
quelle
Verwenden Sie diese DP-Methode von ( /programming/4487438/maximum-sum-of-non-consecutive-elements?rq=1 ):
Bei gegebenem Array A [0..n] sei M (i) die optimale Lösung unter Verwendung der Elemente mit den Indizes 0..i. Dann ist M (-1) = 0 (in der Wiederholung verwendet), M (0) = A [0] und M (i) = max (M (i - 1), M (i - 2) + A [i ]) für i = 1, ..., n. M (n) ist die Lösung, die wir wollen. Das ist O (n) . Sie können ein anderes Array verwenden, um zu speichern, welche Auswahl für jedes Teilproblem getroffen wurde, und so die tatsächlich ausgewählten Elemente wiederherstellen.
Ändern Sie die Rekursion in M (i) = max (M (i - 1), M (i - 2) + A [i]), so dass sie nur dann gespeichert wird, wenn sie durch N teilbar ist
quelle