Решение задач с кузнечиком — это решение задач методом динамического программирования.
Динамическое программирование
Проблемы, где возможны несколько допустимых решений, предполагают возможность выбора одного самого лучшего итогового результата, который может быть осуществлён в теории путём перебора всех возможных вариантов и выбором самого лучшего. Но если объёмы исходных данных достаточно велики, то метод полной переборки вариантов не станет оптимальным по временным затратам.
В таких случаях обычно применяется разбиение большой задачи на ряд более мелких подзадач. Этот способ разрешения больших задач именуется динамическим программированием.
Не все задачи могут быть сведены к динамическому программированию. Задачи, которые возможно решить этим методом, обязаны иметь такие характеристики:
- Задачу можно разбить на ряд подзадач похожего структурного построения, но более маленького объёма.
- В сформированном наборе подзадач можно обнаружить подзадачи с тривиальным уровнем сложности, то есть маленькие и обладающие очевидным решением.
- Наилучшее решение больших подзадач возможно сформировать на базе решений более мелких подзадач.
- Все подзадачные решения возможно представить и сохранить в табличном формате, который имеет не бесконечные размеры.
Все проблемы из сферы динамического программирования можно разделить на два вида:
- Определение числа возможных версий решения. То есть, в данном варианте вычисляется общее число решений.
- Выбор наилучшего решения. В данном варианте оптимизируется целевая функция, то есть находится наилучшее решение из всех возможных решений.
Задача о кузнечике
Задачи, где необходимо найти самое лучшее решение среди множества допустимых вариантов, наиболее просто решаются посредством динамического программирования. Приведём пример задачи поиска оптимального решения на основе задачи о кузнечике, собирающем монеты.
Условия задачи следующие. Кузнечик выполняет серию прыжков по столбам, которые располагаются в ряд по единой линии и на одинаковых дистанциях между ними. Столбы пронумерованы и это номера од единицы до N.В исходном положении кузнечик находится на столбе пол номером один. Он способен совершить прыжок вперёд на дистанцию от одного до К столбов, отсчитывая от текущего его местоположения. При этом, находясь на каждом столбе, у кузнечика есть возможность приобрести или потерять некоторое количество золотых монет. Эта возможность заранее известна для каждого столба. Требуется определить маршрут прыжков кузнечика, чтобы он собрал при этом максимальную сумму золотых монет. При этом существует условие, что прыжки кузнечику разрешены только вперёд.
Рассмотрим исходные данные. В начальной строке можно ввести два натуральных числа N и K (2 ≤ N, K ≤ 10000), которые разделяются при помощи пробела. В следующей строке надо записать также через пробелы N – 2 целых чисел. Это число монет, которые приобретёт кузнечик на каждом столбе, начиная со второго и до N – 1. В случае отрицательного значения числа на столбе, кузнечик потеряет монеты. Есть гарантия, что модуль каждого числа не более десяти тысяч.
Рассмотрим выходные данные. Изначально программе необходимо определить какое самое большое число монет возможно собрать кузнечику. Вторая строка программы должна вычислить количество прыжков кузнечика, а затем определить нумерацию всех столбов, посещённых кузнечиком (по возрастанию номеров через пробелы). При этом, в случае наличия более одного верного решения, можно вывести любое из найденных.
Чтобы решить поставленную задачу, воспользуемся динамическим массивом d[ ]. Здесь d[i] является самым большим количеством золотых монет, которые возможно приобрести кузнечику при нахождении его в текущий момент на столбе i. Исходное наполнение динамического массива: d[1]=0, то есть при расположении кузнечика на первом столбе у него в наличии нуль золотых монет. Определим правило изменения динамического массива:
d[i]=d[num_max]+a[i],
здесь num_max – это нумерация столба, где кузнечик собрал наибольшее число золотых монет, и который был до текущего. То есть, при расположении кузнечика на i-том столбе, ему возможно приобрести самое большое число золотых монет, которое равняется сумме предшествующего самого большого числа монет плюс число монет текущего столба. Решением задачи станет число d[n], где n – номер конечного столба.
Рисунок 1. Решение задачи. Автор24 — интернет-биржа студенческих работ
