Knapsack problem/Continuous: Difference between revisions
Content added Content deleted
m (→version 1: added/changed whitespace and comments, made the program safe from NOVALUE errors.) |
(Added Elixir) |
||
Line 632: | Line 632: | ||
Take all the greaves |
Take all the greaves |
||
Take 3.5kg welt</pre> |
Take 3.5kg welt</pre> |
||
=={{header|Eiffel}}== |
=={{header|Eiffel}}== |
||
<lang Eiffel> |
<lang Eiffel> |
||
Line 714: | Line 715: | ||
Take 3.5kg off welt. |
Take 3.5kg off welt. |
||
The total value is 349.378 |
The total value is 349.378 |
||
</pre> |
|||
=={{header|Elixir}}== |
|||
{{trans|Erlang}} |
|||
<lang elixir>defmodule KnapsackProblem do |
|||
def price_per_weight( items ), do: (for {name, weight, price} <-items, do: {name, weight, price / weight} ) |
|||
def select( max_weight, items ) do |
|||
{_remains, selected_items} = List.foldr( List.keysort(items, 2), {max_weight, []}, &select_until/2 ) |
|||
selected_items |
|||
end |
|||
def task( max_weight, items ) do |
|||
IO.puts "The robber takes the following to maximize the value" |
|||
for {name, weight} <- select( max_weight, price_per_weight(items) ), do: :io.fwrite("~.2f of ~s~n", [weight, name]) |
|||
end |
|||
defp select_until( {name, weight, _price}, {remains, acc} ) when remains > 0 do |
|||
selected_weight = select_until_weight( weight, remains ) |
|||
{remains - selected_weight, [{name, selected_weight} | acc]} |
|||
end |
|||
defp select_until( _item, acc ), do: acc |
|||
defp select_until_weight( weight, remains ) when weight < remains, do: weight |
|||
defp select_until_weight( _weight, remains ), do: remains |
|||
end |
|||
items = [ {"beef", 3.8, 36}, |
|||
{"pork", 5.4, 43}, |
|||
{"ham", 3.6, 90}, |
|||
{"greaves", 2.4, 45}, |
|||
{"flitch", 4.0, 30}, |
|||
{"brawn", 2.5, 56}, |
|||
{"welt", 3.7, 67}, |
|||
{"salami", 3.0, 95}, |
|||
{"sausage", 5.9, 98} ] |
|||
KnapsackProblem.task( 15, items )</lang> |
|||
{{out}} |
|||
<pre> |
|||
The robber takes the following to maximize the value |
|||
3.50 of welt |
|||
2.40 of greaves |
|||
2.50 of brawn |
|||
3.60 of ham |
|||
3.00 of salami |
|||
</pre> |
</pre> |
||