Динамічне програмування. Жадібні алгоритми

Основними типами задач динамічного програмування є:

До задач оптимізації найчастіше належать задачі

У жадібних алгоритмах на кожному кроці із множини можливих варіантів вибирається:

Восьме число у числах Фібоначі дорівнює:

Хто сформулював принцип динамічного програмування:«Оптимальна поведінка має таку властивість:

якими б не були первісний стан і рішення в початковий момент, наступні рішення повинні бути оптимальними щодо стану, отриманого в результаті первісного рішення».

Метод розв’язування задач, що мають певні властивості, шляхом їх розбиття на декілька однотипних підзадач, пов’язаних між собою

Динамічне програмування виникло в

Сутність співоптимальності полягає у тому, що складна задача:

У жадібних алгоритмах після вибору варіанта на даному кроці можна:

Якою не була б інформація, що обробляється, перед черговим етапом необхідно вибрати стратегію на поточному етапі так, щоб виграш на цьому етапі плюс оптимальний виграш на всіх наступних етапах був максимальним.

До задач оптимізації найчастіше належать задачі:

Якщо в касира є монети вартістю 2, 10 і 25 копійок, то повернути здачу 39 копійок можна такою кількістю варіантів: