Algorithmen und Datenstrukturen · Middle · Frage 75 von 75
Subset Sum: können einige der Zahlen target ergeben? Was ist die klassische DP-Lösung?
- 1Die Zahlen sortieren und gierig die größten nehmen, die noch passen
- 2Alle Permutationen der Zahlen probieren und ihre Summen prüfen
- 3Eine boolesche Tabelle erreichbarer Summen, für jede Zahl aktualisiert: O(n × target)
Antwort zeigen
Richtige Antwort: Eine boolesche Tabelle erreichbarer Summen, für jede Zahl aktualisiert: O(n × target)
Erklärung
reachable[s] sagt, ob die Summe s bildbar ist; für jede Zahl aktualisiert man die Summen von hoch nach niedrig, damit sie nur einmal genutzt wird. Greedy kann Lösungen verpassen, und Permutationen sind O(n!). Die DP ist pseudopolynomiell: schnell nur, solange target klein ist.