Dynamic Programming

Ð"ИНАМИЧЕСКОЕ ПРОÐ"РАММИРОÐ'АНИЕ

Метод динамического программирования состоит в разбиении задачи на подзадачи, решении их и объединении результатов. Ð' отличии от метода «разделяй и властвуй», динамическое программирование используется, когда подзадачи не являются независимыми. Чтобы не решать некоторые подзадачи несколько раз (как это делалось бы при использовании стратегии «разделяй и властвуй»), при динамическом программировании подзадачи решаются один раз и результат решения заносится в некоторую таблицу.
Решение задачи методом динамического программирования как правило требует наличия рекуррентного соотношения между подзадачами. Скорость решения задач этим методом как правило полиномиальна, в отличии от методов полного перебора или бектрекинга.

1. Монеты. Имеются монеты достоинством v1, v2, …, vn копеек. Необходимо найти наименьшее количество монет, которыми можно выдать сумму S.

2. Задача о загрузке. Меется судно грузоподъемностью w и n предметов. Известно, что i - ый предмет имеет вес wi и ценность ci. Необходимо загрузить судно предметами так, чтобы...