贪婪的算法实现，Haskell

我需要实现一个Haskell函数，它接收一个Int（卡车负载能力）和一个Ints（可以在卡车上装载的模型框）列表。贪婪的算法实现，Haskell

要定义哪些箱子模型最好放置在卡车中，要求首先将与可用空间关系较大的箱子放在的位置。

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

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

谢谢！

来源

2016-07-15 Breno Henrique

你会怎么做另一种语言？ – ErikR

为什么不是答案[34,34,34]？尝试阅读子集总和问题，并确定您首先需要解决哪些属性。 –

那么这个问题看起来像背包（蛮力将是''maximumBy（比较'总和）。filter（（<= 103）。sum）$ subsequences [15,20,5,45,34]''） - 但这不会允许多次拾取物品 – Carsten

与智能过滤

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]

来源

2016-07-16 01:03:53 karakfa

但大箱子有优先加载。 –

这不是解决方案吗？如果不是规范需要包括元件尺寸和未满足容量之间的折衷。 – karakfa

输出应该是： maximizeLoad 103 [15,20,5,45,34] [45,45,5,5] –

贪婪的算法实现，Haskell

回答

相关问题