小编Gri*_*L. 的帖子

在我尝试学习 Haskell 的过程中，我编写了以下代码来解决一个经典的优化问题。当前的问题是计算销售最大化价格，其中价格单调递增，给定 i 个买家序列，每个买家将以 v_i 的最大价格购买。用数学术语来说：给定 [v_i] ，找到 [p_i] st p_{i+1} >= p_i 最大化 \sum_i q(v_i,p_i) 其中 q(a,b)=0，如果 b>a, q( a,b)=b b<=a

我已经实现了以下代码，使用我认为的自上而下的动态编程方法来解决问题。该算法在每一步都通过最大化剩余序列来决定是否提高价格

maxP::Int->[Int]->(Int,Int)
maxP p [] = (0,p)
maxP p q 
   | a<p = (fst (maxP p (tail q)),p)
   | a==p = (p+fst (maxP p (tail q)),p)
   | otherwise =(maximum l,p+argmax l)
     where a=head q
           pc=[p..a]
           l=zipWith (+) pc $ map (fst)  ( map ((flip maxP) (tail q)) pc )

正如使用 Haskell 时所预期的那样，该代码几乎是 DP 算法的 1-1 实现。该代码返回（销售额，价格水平）

并且，为了获得所有价格序列，为所有 …