69 lines
2.1 KiB
Text
69 lines
2.1 KiB
Text
import mip,util.
|
|
|
|
go =>
|
|
items(AllItems,MaxTotalWeight),
|
|
[Items,Weights,Values] = transpose(AllItems),
|
|
|
|
knapsack_01(Weights,Values,MaxTotalWeight, X,TotalWeight,TotalValues),
|
|
print_solution(Items,Weights,Values, X,TotalWeight,TotalValues),
|
|
nl.
|
|
|
|
% Print the solution
|
|
print_solution(Items,Weights,Values, X,TotalWeight,TotalValues) =>
|
|
println("\nThese are the items to pick:"),
|
|
println(" Item Weight Value"),
|
|
|
|
foreach(I in 1..Items.len)
|
|
if X[I] == 1 then
|
|
printf("* %-25w %3d %3d\n", Items[I],Weights[I], Values[I])
|
|
end
|
|
end,
|
|
nl,
|
|
|
|
printf("Total weight: %d\n", TotalWeight),
|
|
printf("Total value: %d\n", TotalValues),
|
|
nl.
|
|
|
|
% Solve the knapsack problem
|
|
knapsack_01(Weights,Values,MaxTotalWeight, X,TotalWeight,TotalValues) =>
|
|
NumItems = length(Weights),
|
|
|
|
% Variables
|
|
X = new_list(NumItems),
|
|
X :: 0..1,
|
|
|
|
% Constraints
|
|
scalar_product(Weights,X,TotalWeight),
|
|
scalar_product(Values,X,TotalValues),
|
|
TotalWeight #=< MaxTotalWeight,
|
|
|
|
% Search
|
|
Vars = X ++ [TotalWeight, TotalValues],
|
|
solve($[max(TotalValues)], Vars).
|
|
|
|
% data
|
|
items(Items,MaxTotalWeight) =>
|
|
% Item Weight Value
|
|
Items = [["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],
|
|
["suntancream", 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]],
|
|
MaxTotalWeight = 400.
|