Алгоритми та структури даних · Senior · Запитання 24 з 75
Що означає, що DP для рюкзака 0/1 псевдополіноміальне?
- ✓Правильна відповідь: O(n × W) залежить від значення W, а воно експоненційне від кількості його бітів
- 2Воно поліноміальне лише тоді, коли ваги всіх предметів однакові
- 3Воно завжди знаходить наближену відповідь, а не точну
Пояснення
Таблиця має W стовпців, і кожен додатковий біт у W подвоює їх, тож робота експоненційна від розміру вхідних даних. Рюкзак NP-складний; DP швидке лише тоді, коли місткості - малі цілі числа.