How to resolve the algorithm Knapsack problem/Bounded step by step in the Picat programming language
How to resolve the algorithm Knapsack problem/Bounded step by step in the Picat programming language
Table of Contents
Problem Statement
A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature. So he needs some items during the trip. Food, clothing, etc. He has a good knapsack for carrying the things, but he knows that he can carry only 4 kg weight in his knapsack, because they will make the trip from morning to evening. He creates a list of what he wants to bring for the trip, but the total weight of all items is too much. He adds a value to each item. The value represents how important the thing for the tourist. The list contains which items are the wanted things for the trip, what is the weight and value of an item, and how many units does he have from each items.
This is the list:
The tourist can choose to take any combination of items from the list, and some number of each item is available (see the column piece(s) in the list above). He may not cut the items, so he can only take whole units of any item.
Show which items does the tourist carry in his knapsack so that their total weight does not exceed 4 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/Bounded step by step in the Picat programming language
Source code in the picat programming language
import mip,util.
go =>
data(AllItems,MaxWeight),
[Items,Weights,Values,Pieces] = transpose(AllItems),
knapsack_bounded(Weights,Values,Pieces,MaxWeight, X,TotalWeight,TotalValue),
print_solution(Items,Weights,Values, X,TotalWeight,TotalValue),
nl.
% Print the solution
print_solution(Items,Weights,Values, X,TotalWeight,TotalValue) ?=>
println("\nThese are the items to pick:"),
println(" Item Weight Value"),
foreach(I in 1..Items.len)
if X[I] > 0 then
printf("* %d %-29w %3d %3d\n", X[I],Items[I],Weights[I],Values[I])
end
end,
nl,
printf("Total weight: %d\n", TotalWeight),
printf("Total value: %d\n", TotalValue),
nl.
% Solve knapsack problem
knapsack_bounded(Weights,Values,Pieces,MaxWeight, X,TotalWeight,TotalValue) =>
NumItems = length(Weights),
% Variables
MaxPieces = max(Pieces),
X = new_list(NumItems),
X :: 0..MaxPieces,
% Constraints
SumValues = sum(Values),
TotalValue :: 0..SumValues,
TotalWeight :: 0..MaxWeight,
scalar_product(Weights,X,TotalWeight),
scalar_product(Values,X,TotalValue),
TotalWeight #<= MaxWeight,
% Check number of pieces
foreach({XVal,Piece} in zip(X,Pieces))
XVal #=< Piece
end,
% Search
Vars = X ++ [TotalWeight, TotalValue],
solve($[max(TotalValue),down],Vars).
% data
data(Items,MaxWeight) =>
Items =
% Item Weight Value Pieces
[["map", 9, 150, 1],
["compass", 13, 35, 1],
["water", 153, 200, 2],
["sandwich", 50, 60, 2],
["glucose", 15, 60, 2],
["tin", 68, 45, 3],
["banana", 27, 60, 3],
["apple", 39, 40, 3],
["cheese", 23, 30, 1],
["beer", 52, 10, 3],
["suntancream", 11, 70, 1],
["camera", 32, 30, 1],
["T-shirt", 24, 15, 2],
["trousers", 48, 10, 2],
["umbrella", 73, 40, 1],
["waterproof trousers", 42, 70, 1],
["waterproof overclothes", 43, 75, 1],
["note-case", 22, 80, 1],
["sunglasses", 7, 20, 1],
["towel", 18, 12, 2],
["socks", 4, 50, 1],
["book", 30, 10, 2]],
MaxWeight = 400.
You may also check:How to resolve the algorithm Sorting algorithms/Gnome sort step by step in the Kotlin programming language
You may also check:How to resolve the algorithm User input/Text step by step in the Robotic programming language
You may also check:How to resolve the algorithm Memory allocation step by step in the E programming language
You may also check:How to resolve the algorithm Ternary logic step by step in the Julia programming language
You may also check:How to resolve the algorithm Special variables step by step in the Go programming language