Реализация алгоритма Greedy, Haskell

Question

Мне нужно реализовать функцию Haskell, которая получает один Int (грузоподъемность грузовика) и список Ints (модели ящиков, которые могут быть загружены на грузовике).

Чтобы определить, какие коробки модели должны быть размещены предпочтительно в грузовике, он просил, чтобы коробки с большей мощностью в относительно свободного пространства, всегда помещается первым.

Алгоритм должен возвращать список моделей ящиков для размещения на грузовике. Я не знаю, как программировать эту функциональную парадигму:/

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] 

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]