Динамическое программирование в функциональной парадигме

Ответ 1

Всякий раз, когда какая-то часть списка данных вычисляется на основе предыдущего элемента, я думаю о рекурсии Stream. К сожалению, такая рекурсия не может произойти внутри определений или функций методов, поэтому мне пришлось превратить функцию в класс, чтобы она работала.

class IterationForCoin(stream: Stream[Int], coin: Int) {
  val (lower, higher) = stream splitAt coin
  val next: Stream[Int] = lower #::: (higher zip next map { case (a, b) => a + b })
}
val coins = List(1, 2, 5, 10, 20, 50, 100, 200)
val result = coins.foldLeft(1 #:: Stream.fill(200)(0)) { (stream, coin) =>
  new IterationForCoin(stream, coin).next
} last

Определения lower и higher не нужны - я мог бы легко заменить их на stream take coin и stream drop coin, но я думаю, что это немного яснее (и более эффективно) таким образом.

Ответ 2

Я не знаю достаточно о Scala, чтобы прокомментировать это, но типичный способ перевода решения DP в рекурсивный - это memoization (используйте http://en.wikipedia.org/wiki/Memoization). Это в основном кэширование результата вашей функции для всех значений домена

Я нашел это также http://michid.wordpress.com/2009/02/23/function_mem/. НТН

Ответ 3

Функциональное динамическое программирование на самом деле может быть действительно красивым на ленивом языке, например Haskell (там статья об этом на Haskell wiki). Это динамическое программное решение проблемы:

import Data.Array

makeChange :: [Int] -> Int -> Int
makeChange coinsList target = arr ! (0,target)
  where numCoins = length coinsList
        coins    = listArray (0,numCoins-1) coinsList
        bounds   = ((0,0),(numCoins,target))
        arr      = listArray bounds . map (uncurry go) $ range bounds
        go i n   | i == numCoins = 0
                 | otherwise     = let c = coins ! i
                                   in case c `compare` n of
                                        GT -> 0
                                        EQ -> 1
                                        LT -> (arr ! (i, n-c)) + (arr ! (i+1,n))

main :: IO ()
main = putStrLn $  "Project Euler Problem 31: "
                ++ show (makeChange [1, 2, 5, 10, 20, 50, 100, 200] 200)

По общему признанию, это использует память O (cn), где c - количество монет, а n - цель (в отличие от памяти версии O (n) Java); для этого вам придется использовать некоторую технику захвата изменяемого состояния (возможно, STArray). Однако они оба работают в O (cn) времени. Идея состоит в том, чтобы преобразовать рекурсивное решение почти непосредственно рекурсивно, но вместо того, чтобы возвращаться в go, мы просматриваем ответ в массиве. И как мы построим массив? Позвонив по каждому индексу. Поскольку Haskell ленив, он только вычисляет вещи, когда их просят, поэтому порядок оценки, необходимый для динамического программирования, обрабатывается прозрачно.

И благодаря параметрам Scala by-name и lazy val s, мы можем имитировать это решение в Scala:

class Lazy[A](x: => A) {
  lazy val value = x
}

object Lazy {
  def apply[A](x: => A) = new Lazy(x)
  implicit def fromLazy[A](z: Lazy[A]): A = z.value
  implicit def toLazy[A](x: => A): Lazy[A] = Lazy(x)
}

import Lazy._

def makeChange(coins: Array[Int], target: Int): Int = {
  val numCoins = coins.length
  lazy val arr: Array[Array[Lazy[Int]]]
    = Array.tabulate(numCoins+1,target+1) { (i,n) =>
        if (i == numCoins) {
          0
        } else {
          val c = coins(i)
          if (c > n)
            0
          else if (c == n)
            1
          else
            arr(i)(n-c) + arr(i+1)(n)
        }
      }
  arr(0)(target)
}

// makeChange(Array(1, 2, 5, 10, 20, 50, 100, 200), 200)

Класс Lazy кодирует значения, которые оцениваются только по запросу, а затем мы создаем массив, полный их. Оба этих решения работают на целевое значение 10000 практически мгновенно, хотя и намного больше, и вы столкнетесь с переполнением целых чисел или (в Scala, по крайней мере) переполнением стека.

Ответ 4

Хорошо, вот меморированная версия кода Павла Фатина. Я использую материал Memoization Scalaz, хотя очень просто написать собственный класс memoization.

import scalaz._
import Scalaz._

val memo = immutableHashMapMemo[(List[Int], Int), Int]
def f(ms: List[Int], n: Int): Int = ms match {
  case h :: t =>
    if (h > n) 0 else if (n == h) 1 else memo((f _).tupled)(ms, n - h) + memo((f _).tupled)(t, n)
  case _ => 0
} 
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)

Ответ 5

Для полноты, вот небольшой вариант ответа выше, который не использует Stream:

object coins {
  val coins = List(1, 2, 5, 10, 20, 50, 100, 200)
  val total = 200
  val result = coins.foldLeft(1 :: List.fill(total)(0)) { (list, coin) =>
    new IterationForCoin(list, coin).next(total)
  } last
}

class IterationForCoin(list: List[Int], coin: Int) {
  val (lower, higher) = list splitAt coin
  def next (total: Int): List[Int] = {
    val listPart = if (total>coin) next(total-coin) else lower
    lower ::: (higher zip listPart map { case (a, b) => a + b })
  }
}