贪心算法实现，Haskell

Question

我需要实现一个 Haskell 函数，该函数接收一个 Int（卡车负载能力）和一个 Int 列表（可以装载在卡车上的箱子型号）。

定义哪些盒子模型必须优先放置在卡车，要求容量更大的箱子相对于可用 space，总是放在第一位。

该算法应该return 要放置在卡车上的箱子模型列表。我不知道如何编写一个功能范例：/

maximizeLoad 103 [15, 20, 5, 45, 34]
[45, 45, 5, 5]

谢谢！

Answer 1

使用智能过滤的 Bruce force 方法

maximumLoad n = head 
              . head 
              . group length 
              . last 
              . group sum 
              . filter ((<= n) . sum)
              . map concat 
              . sequence 
              . map (rep n)
              . reverse 
              . sort
        where rep n x = take ((div n x)+1) $ iterate (x:) []
              group f = groupBy ((==) `on` f) . sortBy (comparing f) 

> maximumLoad 103 [15, 20, 5, 45, 34]
[34,34,20,15]

UPDATE 对于贪心算法，会简单很多。我认为代码很容易阅读来描述算法。需要反向排序的输入列表。

maxLoad _ [] = []
maxLoad n (x:xs) | n==0 = []
                 | x <= n = x: maxLoad (n-x) (x:xs)
                 | otherwise = maxLoad n xs

> maxLoad 103 $ reverse $ sort [15, 20, 5, 45, 34]
[45,45,5,5]

贪心算法实现，Haskell

Greedy algorithm implementation, Haskell

algorithm

optimization

haskell

maximize