Knapsack problem/Continuous: Difference between revisions
Content added Content deleted
(added ocaml) |
Underscore (talk | contribs) (Added Haskell.) |
||
| Line 34: | 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?''' |
'''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}}== |
=={{header|Java}}== |
||
| Line 264: | Line 305: | ||
2,4 kg greaves (value = 45) |
2,4 kg greaves (value = 45) |
||
3,5 kg welt (value = 63,378)</pre> |
3,5 kg welt (value = 63,378)</pre> |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||