How to resolve the algorithm Knapsack problem/Continuous step by step in the Erlang programming language

Published on 12 May 2024 09:40 PM
#Erlang

How to resolve the algorithm Knapsack problem/Continuous step by step in the Erlang programming language

Table of Contents

Problem Statement

A thief burgles a butcher's shop, where he can select from some items. The thief knows the weights and prices of each items.   Because he has a knapsack with 15 kg maximal capacity, he wants to select the items such that he would have his profit maximized.   He may cut the items;   the item has a reduced price after cutting that is proportional to the original price by the ratio of masses.   That means:   half of an item has half the price of the original.

This is the item list in the butcher's shop:

Show which items the thief carries in his knapsack so that their total weight does not exceed 15 kg, and their total value is maximized.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Knapsack problem/Continuous step by step in the Erlang programming language

Source code in the erlang programming language

-module( knapsack_problem_continuous ).

-export( [price_per_weight/1, select/2, task/0] ).

price_per_weight( Items ) -> [{Name, Weight, Price / Weight} || {Name, Weight, Price} <-Items].

select( Max_weight, Items ) ->
	{_Remains, Selected_items} = lists:foldr( fun select_until/2, {Max_weight, []}, lists:keysort(3, Items) ),
	Selected_items.

task() ->
	Items = items(),
	io:fwrite( "The robber takes the following to maximize the value~n" ),
	[io:fwrite("~.2f of ~p~n", [Weight, Name]) || {Name, Weight} <- select( 15, price_per_weight(Items) )].



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}
	].

select_until( {Name, Weight, _Price}, {Remains, Acc} ) when Remains > 0 ->
	Selected_weight = select_until_weight( Weight, Remains ),
	{Remains - Selected_weight, [{Name, Selected_weight} | Acc]};
select_until( _Item, Acc ) -> Acc.

select_until_weight( Weight, Remains ) when Weight < Remains -> Weight;
select_until_weight( _Weight, Remains ) -> Remains.

You may also check:How to resolve the algorithm CSV to HTML translation step by step in the Oberon-2 programming language
You may also check:How to resolve the algorithm Fibonacci word/fractal step by step in the Delphi programming language
You may also check:How to resolve the algorithm Klarner-Rado sequence step by step in the C programming language
You may also check:How to resolve the algorithm Bernoulli numbers step by step in the Clojure programming language
You may also check:How to resolve the algorithm Lucas-Lehmer test step by step in the Quackery programming language