Algorithmen und Datenstrukturen · Senior · Frage 26 von 75
Was nutzt Bitmasken-DP als Zustand?
- 1Eine ganze Zahl, deren Bits die genutzten Elemente markieren
- 2Ein sortiertes Array der bisher gewählten Elemente
- 3Einen String, der den bisherigen Weg beschreibt
Antwort zeigen
Richtige Antwort: Eine ganze Zahl, deren Bits die genutzten Elemente markieren
Erklärung
Bei n bis etwa 20 passen Teilmengen in eine ganze Zahl: mask | (1 << i) fügt Element i hinzu, mask & (1 << i) prüft es. Zustände wie dp[mask][last] lösen TSP und Zuordnungsprobleme in O(2ⁿ × n²).