Dies ist eine Facebook-Interviewfrage, auf die ich in einem Online-Portal gestoßen bin.
Gegeben eine Menge S, finde alle maximalen Teilmengen, deren Summe & lt; = k. Zum Beispiel, wenn S = {1, 2, 3, 4, 5} und k = 7 Ausgabe ist: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}
Hinweise:
Irgendwelche Ideen wie könnte das gelöst werden?
Ich habe eine Idee - Sie brauchen einen Baum.
Wenn Sie {1, 2, 3, 4, 5} eingegeben haben und nach maximalen Teilmengen suchen, sollten Sie einen Baum ausgehend von den größten Zahlen erstellen und immer while sum <= k erweitern (also nicht bei 4-2 aufhören, aber gehe zu 1, um 4-2-1 zu erhalten.)
Also wären Knoten beginnend mit 5: 5-1 / 5-2 - nur diese 2 haben die Summe & lt; = 7
beginnend mit 4: 4-3 / 4-2-1 / 4-1 (Teilmenge der vorherigen)
beginnend mit 3: 3-2-1 / 3-1 (Teilmenge der vorherigen)
beginnend mit 2: 2-1 (Teilmenge von 3-2-1)
beginnend mit 1: 1 (Teilmenge von 2-1)
Dann können Sie gültige Ausgaben sortieren und erhalten {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}
Ich weiß, es ist zu spät, um zu antworten, aber ich denke, ich habe eine einfache Lösung für dieses Problem gefunden. Wir zählen Teilmengen von S in lexikographischer Reihenfolge mit Backtracking und prüfen die sum der bisher generierten Teilmenge.
Wenn die sum k überschreitet, kommt der interessante Teil: wir müssen überprüfen, ob die generierte subset eine richtige Teilmenge der zuvor gemeldeten Elemente ist.
Eine Lösung besteht darin, alle gemeldeten Teilmengen zu behalten und auf Inklusion zu prüfen, aber es ist verschwenderisch.
Stattdessen berechnen wir die Differenz zwischen k und sum . Wenn es ein Element e in S so gibt, dass e not in subset und e <= (k - sum) , dann ist die von uns erzeugte Menge eine richtige Teilmenge einer zuvor berichteten Teilmenge und wir können sie sicher überspringen.
Hier ist das komplette Arbeitsprogramm im einfachen alten C ++, das die Idee demonstriert:
%Vor%Die Ausgabe sind alle maximalen Teilmengen in lexikographischer Reihenfolge, eine pro Zeile:
%Vor%Dies ist ein Powerset-Problem. Kürzlich fand ich diese Webseite über Algorithmen und es hat meine Vorstellungskraft gemalt: daher folgt die Powerset / Kombinationslösung. Sie können das Programm einfach kopieren, einfügen und ausführen.
%Vor%Eine alte Frage, aber immer noch eine interessante Frage.
Hier ist eine rekursive Java-8-Lösung mit einem "permutativen" Ansatz.
Optimiert für saubereren und kürzeren Code anstelle von Leistung - zum Beispiel müsste das Sortieren und Beschneiden nur einmal stattfinden.
%Vor%Um es zu testen:
%Vor%Algorithmus ist der folgende:
Arbeitslösung für Java ist unten:
%Vor%Es tut mir leid, dass ich so spät abgesprungen bin. Aber wie wäre es damit?
1) Erstellen Sie eine MIN-HEAP-Struktur aus dem angegebenen Array / Set
2) durchqueren Sie die Struktur von der Wurzel und subtrahieren Sie den Wert an dem Knoten, den Sie besuchen. Sobald Sie die erforderliche Summe (curr_sum & gt; k) überschritten haben, geben Sie diesen Pfad aus, gehen Sie zum übergeordneten Objekt zurück und nehmen Sie einen anderen Pfad (dies kann rekursiv erfolgen).
3) Wenn Sie mit Backtracking zum ursprünglichen Knoten zurückkehren, von dem Sie gestartet haben, implementieren Sie den gesamten Algorithmus rekursiv vom linken Knoten root- & gt ;.
4) Machen Sie die gleichen zwei Schritte (2) und (3) oben, aber jetzt mit einem MAX-HEAP.
Ich bin neu in Algorithmen und Datenstrukturen und habe erst begonnen, Intro zu Algos-Cormen zu lesen. Dies könnte eine fehlerhafte Lösung sein, aber ich wäre mehr als glücklich, wenn jemand mir die Schuld aufzeigen würde :)
Tags und Links algorithm arrays computer-science set