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 |
<lang haskell>import Data.List (sortBy) |
||
⚫ | |||
import Data.Ord (comparing) |
import Data.Ord (comparing) |
||
⚫ | |||
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 |
|||
, itemVal, itemWgt :: Rational |
|||
} |
|||
items |
items :: [Bounty] |
||
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 |
|||
⚫ | |||
] |
|||
solution :: [(Rational, Bounty)] |
solution :: [(Rational, Bounty)] |
||
solution = g maxWgt $ sortBy (flip $ comparing f) items |
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)] |
|||
⚫ | |||
main :: IO () |
|||
main = do |
main = do |
||
forM_ solution $ \(w, 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 |
|||
f (w, Bounty _ v wtot) = v * (w / wtot) |
|||
mixedNum q = |
|||
if b == 0 |
|||
then show a |
|||
else printf "%d %d/%d" a (numerator b) (denominator b) |
|||
else printf "%d %d/%d" a (numerator b) (denominator b) |
|||
where |
|||
⚫ | |||
a = floor q |
|||
⚫ | |||
{{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): |