Knapsack problem/Continuous: Difference between revisions
Added Haskell.
(added ocaml) |
Underscore (talk | contribs) (Added Haskell.) |
||
Line 34:
'''Which items does the robber carry in his knapsack so that their total weight does not exceed 15 kg, and their total value is maximised?'''
=={{header|Haskell}}==
We use a greedy algorithm.
<lang haskell>import Control.Monad
import Data.List (sortBy)
import Data.Ord (comparing)
import Text.Printf
maxWgt = 15
data Bounty = Bounty
{itemName :: String,
itemVal, itemWgt :: Rational}
items =
[Bounty "beef" 36 3.8,
Bounty "pork" 43 5.4,
Bounty "ham" 90 3.6,
Bounty "greaves" 45 2.4,
Bounty "flitch" 30 4.0,
Bounty "brawn" 56 2.5,
Bounty "welt" 67 3.7,
Bounty "salami" 95 3.0,
Bounty "sausage" 98 5.9]
solution :: [(Rational, Bounty)]
solution = g maxWgt $ sortBy (flip $ comparing f) items
where g room (b@(Bounty _ _ w) : bs) = if w < room
then (w, b) : g (room - w) bs
else [(room, b)]
f (Bounty _ v w) = v / w
main = do
forM_ solution $ \(w, b) ->
putStrLn $ showRat w ++ " kg of " ++ itemName b
putStrLn $ "Total value: " ++ showRat (sum $ map f solution)
where f (w, Bounty _ v wtot) = v * (w / wtot)
showRat q = printf "%.2f" x
where x = fromInteger (round $ q * 100) / 100 :: Double</lang>
=={{header|Java}}==
Line 264 ⟶ 305:
2,4 kg greaves (value = 45)
3,5 kg welt (value = 63,378)</pre>
=={{header|OCaml}}==
| |||