Алгоритми та структури даних · Senior · Запитання 26 з 75
Що використовує як стан DP по бітових масках?
- ✓Правильна відповідь: Ціле число, біти якого позначають використані елементи
- 2Відсортований масив уже вибраних елементів
- 3Рядок, що описує пройдений шлях
Пояснення
Для n приблизно до 20 підмножини вміщуються в ціле число: mask | (1 << i) додає елемент i, mask & (1 << i) перевіряє його. Стани на кшталт dp[mask][last] розв'язують TSP і задачі призначення за O(2ⁿ × n²).