Таблиця ДП
поточна клітинказвідки беремоваріант, що вигравпредмет узято
Предмети й рюкзак
Зміна будь-якого повзунка будує таблицю заново.
Як рахує модель
T[0][w] = 0 – без предметів цінність нульова.
Якщо вага предмета i більша за w: T[i][w] = T[i−1][w] (предмет не влазить).
Інакше: T[i][w] = max( T[i−1][w] ; T[i−1][w − вагаi] + цінністьi ) – «не брати» або «взяти».
Відповідь – у правому нижньому куті. Відновлення: якщо T[i][w] ≠ T[i−1][w], предмет i взято, і переходимо до w − вагаi.
Клітинок (n+1)·(W+1), кожна – за сталий час: O(n·W) замість 2n перебору.
Що спробувати
- Пройдіть кілька кроків і перевірте: блакитні клітинки завжди в рядку вище. Чому достатньо лише попереднього рядка?
- Зробіть один предмет дуже цінним, але важким (6 кг). За якої місткості рюкзака його починає бути вигідно брати?
- Знайдіть набір, де «жадібний» вибір (брати найдорожчий за кілограм) дає гірший результат, ніж ДП.
- Збільште кількість предметів з 4 до 5: скільки нових клітинок додалося? А скільки нових варіантів для перебору (2n)?
- Поставте всім предметам однакову вагу 1 кг. На що перетворюється задача?
Чому так?
Повний перебір перевіряє всі 2n наборів. Динамічне програмування помічає, що одні й ті самі підзадачі («найкраще з перших i предметів при місткості w») повторюються, тож кожну розв'язує один раз і записує в таблицю.
Кожна клітинка – це вибір між двома вже відомими відповідями: не брати предмет (клітинка зверху) або взяти його (клітинка зверху ліворуч на його вагу + його цінність).
Шкільна програма: інформатика, 9–11 клас (алгоритми, динамічне програмування; олімпіадна підготовка).