Для примера, классическая DP-задача 'Размен монет':
Вам даны монеты определенного достоинства (V1, V2, V3…, VN) необходимо посчитать, какое минимальное количество монет потребуется чтобы набрать заданную сумму S. Количество монет каждого достоинства не ограничено.
Рекуррентная формула для решения этой задачи:
D(S) = 1 + MIN (D(S-Vi))
Где D(S) это минимальное количество монет которое потребуется чтобы набрать сумму S
Как мы это можем реализовать в императивном стиле?
public int change(int[] coins, int s) {
int[] dp = new int[s + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for ( int i = 1; i <= s; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
dp[i] = dp[i - coins[j]] + 1;
}
}
}
return dp[s];
}
В основе этого решения лежит запоминание предыдущих результатов.
Как это решить на Haskell? Ведь мы уже не можем использовать изменяемые массивы или хэш-таблицы. Зато Haskell нам дает в руки такой мощный инструмент как lazy-evaluation. Lazy-evaluation это тоже в своем роде 'запоминание’ только в обратную сторону. Итак решение:
import Array
change :: [Int] -> Int -> Int
change xs n = dp!n
where
dp = listArray (0,n) [ cell i | i<-[0..n]]
cell 0 = 0
cell i = succ$minl [dp!(i-x)| x<-xs, i>=x]
minl :: [Int] -> Int
minl [] = 0
minl xs = minimum xs
Что здесь происходит? Прежде всего, мы создаем массив с решениями
dp = listArray (0,n) [ cell i | i<-[0..n]]
Но в чем особенность? Особенность в том, что значения в этом массиве появляются по-требованию.
cell i = succ$minl [dp!(i-x)| x<-xs, i>x]
Здесь, справа налево, мы вычисляем i-ый элемент массива. Сначала выбираем все монеты достоинство которых меньше либо равно вычисляемой суммы, потом для каждого такого значения смотрим оптимальное решение в массиве. Заметьте, решения там может еще не быть, но оно будет вычислено для нас по-требованию, причем будет вычисленно лишь однажды и лишь для тех значений, которые нам на самом деле нужны! Находим минимальное решение и прибавляем к нему единицу (succ)
Маленькая утилитная функция, которую пришлось ввести minl нужна лишь потому, что стандартная функция minimum не работает с пустыми массивами.
Заключение
В статьях и литературе динамическое программирование как правило приводится с примерами в императивном стиле. Я попытался привести пример решения классической DP задачи в функциональном стиле, который, надеюсь, может оказаться для кого-то полезным.
step-up your cholesterol, which carries the LDL cholesterol bad cholesterol to the liver to be reddened out of the dead body.
ReplyDeleteAlong with meter the share of issue forth out with a
buggy, creamy smooothie that is levelheaded as can be. In France, red
Wine-colored -- a meal, alternatively of relying on the fats in the animate being products to ply the
taste of the food. This discipline launch an Association normal
limits testament likewise upshot in a decreased viscosity
of the roue.
my homepage :: cholesterol treating niacin with high
Очень интересно. Мне нравится, и даже в качестве заработка. Не всегда же на https://cryptograph.life/post_crypto/kak-torgovat-s-plechom-na-birzhe-kriptovalyut-v-2020-godu-instrukciya-po-marzhinalnoy-torgovle зарабатывать)надо пробовать разные вещи)
ReplyDeleteВ выборе криптовалютных бирж, стоит обратить внимание на https://cryptograph.life/post_crypto/slovar-treydera-kriptovalyut-osnovnye-terminy
ReplyDeleteМне и еще нравится этот сайт,
https://cryptograph.life/post_crypto/kak-realizovat-strategii-kriptovalyutnogo-treydinga
https://www.0642.ua/list/268870
скажите, а что выгодней заниматься криптой или агробизнес прочитала новость 18 млн $ в Евротерминал, развитие агробизнеса, энергоэффективности, кредитования и других секторов экономики — что сделал ЕБРР в Украине
ReplyDelete