相关疑难解决方法(0)

Haskell和其他函数式编程语言是在不维护状态的前提下构建的.我还不熟悉函数式编程的工作原理和概念,所以我想知道是否有可能以FP方式实现DP算法.

可以使用哪些函数式编程结构来做到这一点？

SPOILERS:我正在http://www.spoj.pl/problems/KNAPSACK/上工作,所以如果你不想为你破坏可能的解决方案,请不要偷看.

样板:

import Data.Sequence (index, fromList)
import Data.MemoCombinators (memo2, integral)

main = interact knapsackStr

knapsackStr :: String -> String
knapsackStr str = show $ knapsack items capacity numItems
  where [capacity, numItems] = map read . words $ head ls
        ls = lines str
        items = map (makeItem . words) $ take numItems $ tail ls

设置舞台的一些类型和帮助:

type Item = (Weight, Value)
type Weight = Int
type Value = Int

weight :: Item -> Weight
weight = fst

value …