Lập trình động trong mô hình chức năng

Question

Tôi đang xem Problem thirty one trên Project Euler, hỏi có bao nhiêu cách khác nhau để tạo ra £ 2 bằng cách sử dụng số tiền 1p, 2p, 5p, 10p, 20p, 50p, £ 1 (100p) và £ 2 (200p).

Có nhiều giải pháp đệ quy như thế này ở Scala (tín dụng cho 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) 

và mặc dù nó chạy đủ nhanh, nó tương đối hiệu quả, gọi f chức năng khoảng 5,6 triệu lần.

tôi thấy giải pháp của người khác trong Java được lập trình tự động (tín dụng để wizeman từ Bồ Đào Nha)

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

Đây là hiệu quả hơn và vượt qua các vòng trong chỉ 1220 lần.

Trong khi tôi rõ ràng có thể dịch nguyên văn này ít nhiều thành Scala khi sử dụng các đối tượng Array, có cách chức năng thành ngữ để thực hiện điều này bằng cấu trúc dữ liệu không thay đổi được không?

Tôi đã cố gắng và trở nên khó khăn khi cố gắng đệ quy cập nhật List trước khi quyết định tôi có thể đang tiếp cận nó theo cách sai.

Answer 1

Bất cứ khi nào một phần nào đó của danh sách dữ liệu được tính toán dựa trên yếu tố trước đó, tôi nghĩ đến việc đệ quy Stream. Thật không may, đệ quy như vậy không thể xảy ra bên trong các định nghĩa hoặc hàm của phương thức, vì vậy tôi phải chuyển một hàm thành một lớp để làm cho nó hoạt động.

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 

Các định nghĩa của lower và higher là không cần thiết - tôi có thể dễ dàng thay thế chúng với stream take coin và stream drop coin, nhưng tôi nghĩ rằng đó là rõ ràng hơn một chút (và hiệu quả hơn) theo cách này.

Answer 2

Tôi không biết đủ về Scala để nhận xét cụ thể về điều đó, nhưng cách điển hình để dịch một giải pháp DP trong một đệ quy là ghi nhớ (sử dụng http://en.wikipedia.org/wiki/Memoization). Điều này về cơ bản là lưu vào bộ nhớ cache kết quả của hàm của bạn cho tất cả các giá trị của miền

Tôi cũng tìm thấy giá trị này http://michid.wordpress.com/2009/02/23/function_mem/. HTH

Answer 3

Ok, đây là phiên bản được ghi nhớ của mã Pavel Fatin. Tôi đang sử dụng công cụ ghi nhớ Scalaz, mặc dù thật đơn giản để viết lớp ghi nhớ của riêng bạn.

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 4

lập trình năng động chức năng thực sự có thể được thực sự xinh đẹp trong một ngôn ngữ lười biếng, chẳng hạn như Haskell (có an article on it trên wiki Haskell). Đây là một giải pháp quy hoạch động để các vấn đề:

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) 

Phải thừa nhận rằng, điều này sử dụng O (cn) bộ nhớ, nơi c là số tiền xu và n được mục tiêu (như trái ngược với Bộ nhớ O (n) của phiên bản Java); để có được điều đó, bạn phải sử dụng một số kỹ thuật chụp trạng thái có thể thay đổi (có thể là STArray).Tuy nhiên, cả hai đều chạy trong thời gian O (cn). Ý tưởng là mã hóa giải pháp đệ quy gần như trực tiếp đệ quy, nhưng thay vì đệ quy trong phạm vi , hãy truy cập, chúng tôi tra cứu câu trả lời trong mảng. Và làm thế nào để chúng tôi xây dựng mảng? Bằng cách gọi , hãy truy cập trên mọi chỉ mục. Kể từ khi Haskell là lười biếng, nó chỉ tính toán những điều khi được yêu cầu, do đó, thứ tự đánh giá các công cụ cần thiết cho lập trình năng động là tất cả xử lý minh bạch.

Và nhờ vào các thông số theo tên Scala và lazy val s, chúng ta có thể bắt chước giải pháp này trong 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) 

Lớp Lazy mã hóa các giá trị mà chỉ được đánh giá theo yêu cầu, và sau đó chúng ta xây dựng một mảng đầy đủ của họ. Cả hai giải pháp này đều hoạt động với giá trị đích thực là 10000, mặc dù đi lớn hơn nhiều và bạn sẽ chạy vào tràn số nguyên hoặc (trong Scala, ít nhất) một tràn ngăn xếp.

Answer 5

Vì lợi ích của sự hoàn chỉnh, đây là một biến thể nhẹ của câu trả lời ở trên mà không sử dụng 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 }) 
    } 
}