Knapsack problem/Continuous: Difference between revisions
→{{header|Haskell}}: hlint, hindent, minor tidying
(Added Kotlin) |
(→{{header|Haskell}}: hlint, hindent, minor tidying) |
||
Line 1,267:
We use a greedy algorithm.
<lang haskell>import
import Data.List (sortBy)▼
import Data.Ord (comparing)
import Control.Monad (forM_)
import Data.Ratio (numerator, denominator)
maxWgt :: Rational
maxWgt = 15
data Bounty = Bounty
}
items
items =
[Bounty "beef" 36 3.8,▼
]
solution :: [(Rational, Bounty)]
solution = g maxWgt $ sortBy (flip $ comparing f) items
where
where g room (b@(Bounty _ _ w) : bs) = if w < room▼
g
if w <
else [(room, b)]
main :: IO ()
main = do
where
if b ==
then show a
else printf
where
b = q - toEnum a</lang>▼
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):
| |||