Архив категории ‘Динамическое программирование’

Задача «Копилка»

    Здесь мы разберем решение задачи "Копилка".     Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность Pi и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.     Ограничения: 1 ≤ E ≤ F […]

Задача «Маршрут»

    Здесь мы разберем решение задачи "Маршрут".     Дана матрица N*N, заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути […]

Задача «Чебурашка»

    Здесь мы разберем решение задачи "Чебурашка".     В таблице размером N*N, где N<13, клетки заполнены случайным образом цифрами от 0 до 9. Предложить Чебурашке алгоритм, позволяющий найти маршрут из клетки (1, 1) в клетку (N, N) и удовлетворяющий следующим условиям: любые две последовательные клетки в маршруте имеют общую сторону; количество клеток маршрута минимально; сумма […]

Задача о НОП

    Здесь мы разберем решение задачи о НОП.     В различных биологических задачах часто необходимо сравнивать ДНК двух или нескольких организмов. Моделью молекулы ДНК можно считать строку, над алфавитом из четырех символов (А, Г, Ц, Т). Тогда поставить задачу можно следующим образом: даны две строки, требуется найти подпоследовательность наибольшей длины, входящую в оба слова. Теперь […]

Задача «Головоломка умножения»

    Здесь мы разберем решение задачи "Головоломка умножения".     В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от нее. Не […]

Задача «Перемножение нескольких матриц»

    Здесь мы разберем решение задачи "Перемножение нескольких матриц".     Дана последовательность из n матриц заданных размеров [A1, A2, ..., An] (матрица Ai имеет размер pi-1 на pi ); требуется найти такую (полную) расстановку скобок в произведении A1A2 ... An, чтобы вычисление произведения требовало наименьшего числа умножений и найти результат перемножения этих матриц. [1, с.289]. […]

Примеры задач, решаемые методом динамического программирования

    Здесь мы разберем несколько задач, решаемых методом динамического программирования.     Дана последовательность из n матриц заданных размеров [A1, A2, ..., An] (матрица Ai имеет размер pi-1 на pi ); требуется найти такую (полную) расстановку скобок в произведении A1A2 ... An, чтобы вычисление произведения требовало наименьшего числа умножений и найти результат перемножения этих матриц. [1, […]

Динамическое программирование «сверху вниз» и «снизу вверх»

   На этом шаге мы рассмотрим понятия динамическое программирование "сверху вниз" и "снизу вверх".    Возможно два варианта вычисления оптимального значения параметра для всей задачи (этап 3 алгоритма решения задач методом динамического программирования):    Если задачу решаем рекурсивно, значит, процедура делит заданную ей задачу на подзадачи (предварительно выяснив, не является ли задача тривиальной, и, проверив, не решалась ли […]

Случаи, когда применимо динамическое программирование

    На этом шаге мы рассмотрим случаи, когда применимо динамическое программирование.     Существует два признака, характерных для задач, решаемых методом динамического программирования: Оптимальность для подзадач. В задаче имеются перекрывающиеся подзадачи.     Рассмотрим более подробно эти признаки. Оптимальность для подзадач    При решении оптимизационной задачи с помощью динамического программирования необходимо сначала описать структуру оптимального решения. Будем говорить, […]

Вероятностное динамическое программирование

    На этом шаге мы рассмотрим вероятностное динамическое программирования.     Выделяют два вида динамического программирования: детерминированное и вероятностное. [1, c 562].    Вероятностное динамическое программирование отличается от детерминированного динамического программирования тем, что состояния и прибыли на каждом этапе являются случайными. Модели вероятностного динамического программирования возникают, в частности, при рассмотрении стохастических моделей управления запасами и в теории […]