Knapsack problem/Bounded: Difference between revisions
→{{header|Picat}}
Line 3,227:
cache_entries:0, hits:0, misses:33615741
</pre>
=={{header|Picat}}==
<lang Picat>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.</lang>
Output:
<pre>These are the items to pick:
Item Weight Value
* 1 map 9 150
* 1 compass 13 35
* 1 water 153 200
* 2 glucose 15 60
* 3 banana 27 60
* 1 cheese 23 30
* 1 suntancream 11 70
* 1 waterproof overclothes 43 75
* 1 note-case 22 80
* 1 sunglasses 7 20
* 1 socks 4 50
Total weight: 396
Total value: 1010</pre>
=={{header|PicoLisp}}==
| |||