Algorytmy i struktury danych · Senior · Pytanie 24 z 75
Co oznacza, że DP dla plecaka 0/1 jest pseudowielomianowe?
- ✓Poprawna odpowiedź: O(n × W) zależy od wartości W, która jest wykładnicza względem liczby jej bitów
- 2Jest wielomianowe tylko wtedy, gdy wagi wszystkich przedmiotów są równe
- 3Zawsze znajduje przybliżoną odpowiedź, nigdy dokładną
Wyjaśnienie
Tabela ma W kolumn, a każdy dodatkowy bit w W je podwaja, więc praca jest wykładnicza względem rozmiaru danych. Plecak jest NP-trudny; DP jest szybkie tylko wtedy, gdy pojemności to małe liczby całkowite.