贪婪算法实现

Question

我需要实现一个Haskell函数，它接收一个Int (卡车承载能力)，以及一个Int列表(可以加载到卡车上的盒子模型)。

为了确定哪种箱体模型最好放在卡车上，要求在可用空间方面容量更大的箱子总是放在第一位。

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

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

谢谢!

Answer 1

带智能滤波的Bruce方法

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]

更新的贪婪算法，它会简单得多。我认为代码很容易读来描述算法。期望反向排序输入列表。

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]