72 lines
2.4 KiB
Erlang
72 lines
2.4 KiB
Erlang
-module(knapsack_0_1).
|
|
|
|
-export([go/0,
|
|
solve/5]).
|
|
|
|
-define(STUFF,
|
|
[{"map", 9, 150},
|
|
{"compass", 13, 35},
|
|
{"water", 153, 200},
|
|
{"sandwich", 50, 160},
|
|
{"glucose", 15, 60},
|
|
{"tin", 68, 45},
|
|
{"banana", 27, 60},
|
|
{"apple", 39, 40},
|
|
{"cheese", 23, 30},
|
|
{"beer", 52, 10},
|
|
{"suntan cream", 11, 70},
|
|
{"camera", 32, 30},
|
|
{"T-shirt", 24, 15},
|
|
{"trousers", 48, 10},
|
|
{"umbrella", 73, 40},
|
|
{"waterproof trousers", 42, 70},
|
|
{"waterproof overclothes", 43, 75},
|
|
{"note-case", 22, 80},
|
|
{"sunglasses", 7, 20},
|
|
{"towel", 18, 12},
|
|
{"socks", 4, 50},
|
|
{"book", 30, 10}
|
|
]).
|
|
|
|
-define(MAX_WEIGHT, 400).
|
|
|
|
go() ->
|
|
StartTime = os:timestamp(),
|
|
{ItemList, TotalValue, TotalWeight} =
|
|
solve(?STUFF, ?MAX_WEIGHT, [], 0, 0),
|
|
TimeElapsed = timer:now_diff(os:timestamp(), StartTime),
|
|
io:format("Items: ~n"),
|
|
[io:format("~p~n", [Item]) || Item <- ItemList],
|
|
io:format(
|
|
"Total value: ~p~nTotal weight: ~p~nTime elapsed in milliseconds: ~p~n",
|
|
[TotalValue, TotalWeight, TimeElapsed/1000]).
|
|
|
|
solve([], _TotalWeight, ItemAcc, ValueAcc, WeightAcc) ->
|
|
{ItemAcc, ValueAcc, WeightAcc};
|
|
solve([{_Item, ItemWeight, _ItemValue} | T],
|
|
TotalWeight,
|
|
ItemAcc,
|
|
ValueAcc,
|
|
WeightAcc) when ItemWeight > TotalWeight ->
|
|
solve(T, TotalWeight, ItemAcc, ValueAcc, WeightAcc);
|
|
solve([{ItemName, ItemWeight, ItemValue} | T],
|
|
TotalWeight,
|
|
ItemAcc,
|
|
ValueAcc,
|
|
WeightAcc) ->
|
|
{_TailItemAcc, TailValueAcc, _TailWeightAcc} = TailRes =
|
|
solve(T, TotalWeight, ItemAcc, ValueAcc, WeightAcc),
|
|
{_HeadItemAcc, HeadValueAcc, _HeadWeightAcc} = HeadRes =
|
|
solve(T,
|
|
TotalWeight - ItemWeight,
|
|
[ItemName | ItemAcc],
|
|
ValueAcc + ItemValue,
|
|
WeightAcc + ItemWeight),
|
|
|
|
case TailValueAcc > HeadValueAcc of
|
|
true ->
|
|
TailRes;
|
|
false ->
|
|
HeadRes
|
|
end.
|