82 lines
2.4 KiB
Plaintext
82 lines
2.4 KiB
Plaintext
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.
|