貪婪的算法實現，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

回答

相關問題