Algorytmy i struktury danych · Senior · Pytanie 26 z 75
Czego DP na maskach bitowych używa jako stanu?
- ✓Poprawna odpowiedź: Liczby całkowitej, której bity oznaczają użyte elementy
- 2Posortowanej tablicy dotąd wybranych elementów
- 3Napisu opisującego przebytą ścieżkę
Wyjaśnienie
Dla n do około 20 podzbiory mieszczą się w liczbie całkowitej: mask | (1 << i) dodaje element i, mask & (1 << i) go sprawdza. Stany typu dp[mask][last] rozwiązują TSP i problemy przydziału w O(2ⁿ × n²).