函数式编程中的动态规划

Question

我正在看 Project Euler 上的 问题31，它问：使用任意数量的1p、2p、5p、10p、20p、50p、£1（100p）和£2（200p）硬币，有多少种不同的方法可以组成 £2。

有递归解决方案，例如 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，但是否有一种惯用的函数式方法，可以使用不可变数据结构来做到这一点，最好具有类似的简洁性和性能？

我尝试过在递归更新列表之前卡住了，后来认为我可能只是走错了路。

- Luigi Plinge

---

我看了 Scala 版本 1 分钟就能明白它是如何工作的。而 Java 版本我看了 5 分钟，仍然不知道它是如何工作的。这个例子很好地展示了函数式编程并不比命令式编程更复杂。 - huynhjl

除了观察一个功能性和迫切性算法外，同时也在看一个经典和优化的算法。 - ziggystar

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，但我认为这样更清晰（也更高效）。

- Daniel C. Sobral

---

这里真正发挥作用的是流吗？还是高低值被重复使用（所以这是“存储”技巧，可以防止重复劳动的关键）？ - PeteyPabPro

@PeteyPabPro 两者都是。Stream 可以使数据递归成为可能，从而实现重用。 - Daniel C. Sobral

@DanielCSobral 但是可以创建一个没有 Stream 的稍微修改过的版本，对吗？（请参见下面我的答案）。 - PeteyPabPro

也许看看如何使用惰性数据结构来进行动态编程会很有趣：http://www.haskell.org/haskellwiki/Dynamic_programming_example - Mysterious Dan

Answer 2

我对Scala不是很了解，无法就此发表具体评论。但将动态规划（DP）解决方案转换为递归解决方案的典型方法是通过记忆化（使用http://en.wikipedia.org/wiki/Memoization）。这基本上是为定义域内所有值缓存函数结果。

我也找到了这篇文章：http://michid.wordpress.com/2009/02/23/function_mem/，希望能帮到你。

- dfb

---

虽然这个解决方案能够正常工作并且是我最喜欢的，但我发现它存在巨大的性能问题。在Scala 2.8.1上，使用while循环处理数组是迄今为止最有效的解决方案，至少可以提高十倍以上的效率。 - Raphael

@Raphael：当运行时间仅为几毫秒时，十倍左右的因素并不重要！ - Gareth Rees

@Luigi：Raphael和我正在比较动态规划和递归加记忆化，而不是单独的递归。 - Gareth Rees

如果有人知道该怎么做，我很想看看备忘录技术可以被实现得多简洁... :) - Luigi Plinge

我将（整数的）元组用作映射键。在我的情况下，我们讨论的是90分钟与“12小时后中止”，而不是毫秒。对代码进行分析显示了 _大量_的（非）装箱操作，但大部分时间都花在了检索用于存储的哈希映射中的值上。我猜它们散布在堆上，没有利用访问的局部性（就像数组循环一样）。 - Raphael

Answer 3

函数式动态规划在惰性语言（比如Haskell）中实际上可以非常优美（Haskell维基上有一篇文章）。以下是该问题的动态规划解决方案：

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 中递归，而是在数组中查找答案。我们如何构造数组？通过在每个索引上调用 go。由于 Haskell 是惰性的，所以只有在被要求计算时它才会进行计算，因此动态编程所必需的顺序评估部分都被透明地处理。

由于 Scala 的按名称参数和 lazy val，我们可以在 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)

< p > Lazy类编码的是只有在需要时才进行计算的值，然后我们构建一个由它们填充的数组。这两种解决方案对于目标值为10000的情况几乎可以立即得到结果，但如果更大，您将会遇到整数溢出或（至少在Scala中）堆栈溢出的问题。

- Antal Spector-Zabusky

Answer 4

好的，这是Pavel Fatin代码的记忆化版本。我使用了Scalaz的记忆化工具，尽管编写自己的记忆化类也非常简单。

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)

- Daniel C. Sobral

---

@Luigi，你使用的堆栈太小了。 :-) 溢出与记忆化无关--因为有两个对 f 的调用，其中一个永远不会是尾递归。在这种情况下，考虑第一个调用将使用相同的 ms 参数进行递归，每次将 n 减少 h，直到 n == h 或 h > n。当第一次调用时，n 将从 750 开始，h 为 1，因此它将递归 750 次。我试过十磅没有问题，但我通常设置 -Xss1m。 - Daniel C. Sobral

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

- PeteyPabPro