功能范式中的动态编程

Question

我正在寻找关于项目欧拉的问题三十一,请问,有多少不同的方法可以使用任意数量的1p,2p,5p,10p,20p,50p,£1(100p)和£的硬币赚2英镑2(200p).

有递归解决方案,例如Scala中的这个解决方案(由Pavel Fatin提供)

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

虽然运行速度足够快,但它的效率相对较低,调用f函数大约560万次.

我看到了其他用Java编写的动态编程解决方案(来自葡萄牙的wizeman)

final static int TOTAL = 200;

public static void main(String[] args) {
    int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
    int[] ways = new int[TOTAL + 1];
    ways[0] = 1;

    for (int coin : coins) {
        for (int j = coin; j <= TOTAL; j++) {
            ways[j] += ways[j - coin];
        }
    }

    System.out.println("Result: " + ways[TOTAL]);
}

这样效率更高,内循环仅传递1220次.

虽然我可以使用Array对象将这或多或少地逐字翻译成Scala ,但使用不可变数据结构是否有一种惯用的功能方法,最好具有类似的简洁性和性能？

我已经尝试过,并试图以递归方式更新a List之前决定我可能只是以错误的方式接近它.

Answer 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,但我认为这种方式更清晰(更有效).

Answer 2

我不太了解Scala对此有何​​具体评论,但将DP解决方案转换为递归方法的典型方法是记忆(使用http://en.wikipedia.org/wiki/Memoization).这基本上是为域的所有值缓存函数的结果

我也发现了这个问题http://michid.wordpress.com/2009/02/23/function_mem/.HTH

Answer 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是目标(与Java版本的O(n)内存相对); 为此,你必须使用一些捕获可变状态的技术(可能是一个STArray).但是,它们都在O(cn)时间运行.我们的想法是几乎直接递归地对递归解决方案进行编码,但不是在go中递归,而是在数组中查找答案.我们如何构建数组？通过调用去的各项指标.由于Haskell是懒惰的,它只会在被要求时计算,所以动态编程所需的评估顺序都是透明处理的.

感谢Scala的名字参数和lazy vals,我们可以在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中)堆栈溢出.

Answer 4

好的,这是Pavel Fatin代码的备忘版本.我正在使用Scalaz memoization东西,尽管编写自己的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)

Answer 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 })
  }
}