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.