Knapsack problem/Continuous: Difference between revisions

Content added Content deleted

Inline

@@ Line 789: / Line 789: @@
 {{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
+    Enum.sort_by( items, fn {_name, weight, price} -> - price / weight end )
-    {_remains, selected_items} = List.foldr( List.keysort(items, 2), {max_weight, []}, &select_until/2 )
+    |> Enum.reduce( {max_weight, []}, &select_until/2 )
-    selected_items
+    |> elem(1)
+    |> Enum.reverse
   end
-  def task( max_weight, items ) do
+  def task( items, max_weight ) 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])
+    Enum.each( select( max_weight, items ), fn {name, weight} ->
+      :io.fwrite("~.2f of ~s~n", [weight, name])
+    end )
   end
@@ Line 821: / Line 823: @@
           {"sausage", 5.9, 98} ]
-KnapsackProblem.task( 15, items )</lang>
+KnapsackProblem.task( items, 15 )</lang>
 {{out}}
 <pre>
 The robber takes the following to maximize the value
-.50 of welt
-.40 of greaves
-.50 of brawn
-.60 of ham
 .00 of salami
+.60 of ham
+.50 of brawn
+.40 of greaves
+.50 of welt
+</pre>
+===Alternate Version===
+{{trans|Ruby}}
+<lang elixir>defmodule KnapsackProblem do
+  def continuous(items, max_weight) do
+    Enum.sort_by(items, fn {_item, {weight, price}} -> -price / weight end)
+    |> Enum.reduce_while({max_weight,0}, fn {item, {weight, price}}, {rest, value} ->
+         if rest > weight do
+           IO.puts "Take all #{item}"
+           {:cont, {rest - weight, value + price}}
+         else
+           :io.format "Take ~.3fkg of ~s~n~n", [rest, item]
+           :io.format "Total value of swag is ~.2f~n", [value + rest*price/weight]
+           {:halt, :ok}
+         end
+       end)
+    |> case do
+         {weight, value} ->
+             :io.format "Total:  weight ~.3fkg, value ~p~n", [max_weight-weight, value]
+         x -> x
+       end
+  end
+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.continuous( items, 15 )</lang>
+{{out}}
+<pre>
+Take all salami
+Take all ham
+Take all brawn
+Take all greaves
+Take 3.500kg of welt
+Total value of swag is 349.38
 </pre>