Tuesday, June 1, 2010

Динамическое программирование на Хаскеле, часть 2

Этот пост является продолжением моего предыдущего поста про использование Haskell в динамическом программировании.
Давайте немного усложним задачу. Пусть теперь нам требуется не просто вернуть минимальное количество монет, которое требуется чтобы разменять заданную сумму, а нужно вернуть список монет.
Как это реализуется с точки зрения DP? В предыдущем решении для каждой суммы мы сохраняли оптимальное значение. Теперь нам нужно дополнительно хранить список монет, приведших к данному значению. Решение в лоб: связать с каждым элементом массива список в котором будет хранится полный перечень используемых монет. Этот подход не очень рационален с точки зрения используемой памяти. Куда лучше хранить лишь дельту. То есть, для каждой суммы мы храним значение последней добавленной монеты. Тогда, после того как решение найдено, мы можем пройти по этим дельтам в обратную сторону и собрать все монеты которые были использованы. Итак, переходим от слов к делу.
Решение на императивном языке Java будет выглядеть следующим образом:
  
public int[] change(int[] coins, int s) {
int[] dp = new int[s + 1];
int[] backtrack = 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;
backtrack[i] = i - coins[j];
}

}
}
int[] res = new int[dp[s]];
int i = s;
int n = 0;
while(i!=0){
res[n++] = i-backtrack[i];
i = backtrack[i];
}
return res;
}


Как написать аналогичное решение на Haskell? Достаточно просто. Для этого на помощь нам приходят кортежи (они же туплы). Очень удобная структура данных имеющаяся в любом функциональном языке программирования.
По сути, кортеж, это просто набор элементов. Элементы могут быть одного а могут быть разных типов. Объявляются кортежи в Haskell очень просто:

  
let a = (1, 2)


a – это кортеж из двух элементов 1 и 2.
Чтобы достать элемент из кортежа, мы можем использовать функции fst, snd или pattern matching.
Теперь собственно решение. Идея та же, что и в императивном подходе. Только теперь мы не заводим дополнительный массив, а прямо в исходном массиве храним кортежи со связкой: оптимальное значение – величина последней монеты.
  
import Array
import Data.List


minl :: [(Int, Int)] -> (Int, Int)
minl [] = (0, 0)
minl xs = minimumBy (\x y -> compare (fst x) (fst y)) xs

changeValues :: [Int] -> Int -> [Int]
changeValues xs n = extract dp n
where
dp = listArray (0,n) [ cell i | i<-[0..n]]
cell 0 = (0, 0)
cell i = minl [(succ$fst (dp!(i-x)), x) | x<-xs, i>=x]
extract dp 0 = []
extract dp n = (snd (dp!n)):(extract dp (n-(snd (dp!n))))


Пришлось добавить функцию extract которая достает из массива dp величины монет (т.е., вторые элементы) и складывает их в результирующий список.

No comments:

Post a Comment