Knapsack problem/Continuous: Difference between revisions

Content added Content deleted
(Added Kotlin)
(→‎{{header|Haskell}}: hlint, hindent, minor tidying)
Line 1,267: Line 1,267:
We use a greedy algorithm.
We use a greedy algorithm.


<lang haskell>import Control.Monad
<lang haskell>import Data.List (sortBy)
⚫
import Data.List (sortBy)
import Data.Ord (comparing)
import Data.Ord (comparing)
⚫
import Text.Printf (printf)
import Control.Monad (forM_)
import Data.Ratio (numerator, denominator)
import Data.Ratio (numerator, denominator)
import Text.Printf


maxWgt :: Rational
maxWgt = 15
maxWgt = 15


data Bounty = Bounty
data Bounty = Bounty
{itemName :: String,
{ itemName :: String
itemVal, itemWgt :: Rational}
, itemVal, itemWgt :: Rational
}


items =
items :: [Bounty]
items =
⚫
[Bounty "beef" 36 3.8,
Bounty "pork" 43 5.4,
[ Bounty "beef" 36 3.8
Bounty "ham" 90 3.6,
, Bounty "pork" 43 5.4
Bounty "greaves" 45 2.4,
, Bounty "ham" 90 3.6
Bounty "flitch" 30 4.0,
, Bounty "greaves" 45 2.4
Bounty "brawn" 56 2.5,
, Bounty "flitch" 30 4.0
Bounty "welt" 67 3.7,
, Bounty "brawn" 56 2.5
Bounty "salami" 95 3.0,
, Bounty "welt" 67 3.7
Bounty "sausage" 98 5.9]
, Bounty "salami" 95 3.0
⚫
, Bounty "sausage" 98 5.9
]


solution :: [(Rational, Bounty)]
solution :: [(Rational, Bounty)]
solution = g maxWgt $ sortBy (flip $ comparing f) items
solution = g maxWgt $ sortBy (flip $ comparing f) items
where
⚫
where g room (b@(Bounty _ _ w) : bs) = if w < room
then (w, b) : g (room - w) bs
g room (b@(Bounty _ _ w):bs) =
else [(room, b)]
if w < room
f (Bounty _ v w) = v / w
then (w, b) : g (room - w) bs
else [(room, b)]
⚫
f (Bounty _ v w) = v / w


main :: IO ()
main = do
main = do
forM_ solution $ \(w, b) ->
forM_ solution $ \(w, b) -> printf "%s kg of %s\n" (mixedNum w) (itemName b)
printf "%s kg of %s\n" (mixedNum w) (itemName b)
(printf "Total value: %s\n" . mixedNum . sum) $ f <$> solution
where
printf "Total value: %s\n" $ mixedNum $ sum $ map f solution
where f (w, Bounty _ v wtot) = v * (w / wtot)
f (w, Bounty _ v wtot) = v * (w / wtot)
mixedNum q = if b == 0
mixedNum q =
then show a
if b == 0
then show a
else printf "%d %d/%d" a (numerator b) (denominator b)
where a = floor q
else printf "%d %d/%d" a (numerator b) (denominator b)
where
⚫
b = q - toEnum a</lang>
a = floor q
⚫
b = q - toEnum a</lang>
{{Out}}
<pre>3 kg of salami
3 3/5 kg of ham
2 1/2 kg of brawn
2 2/5 kg of greaves
3 1/2 kg of welt
Total value: 349 14/37</pre>


Or similar to above (but more succinct):
Or similar to above (but more succinct):
Retrieved from "https://rosettacode.org/wiki/Knapsack_problem/Continuous"