% 
% Knapsack (Unbounded) in MiniZinc.
% 
% http://rosettacode.org/wiki/Knapsack_problem/Unbounded
% """
% A traveller gets diverted and has to make an unscheduled stop in what 
% turns out to be Shangri La. Opting to leave, he is allowed to take as much 
% as he likes of the following items, so long as it will fit in his knapsack, 
% and he can carry it. He knows that he can carry no more than 25 'weights' in 
% total; and that the capacity of his knapsack is 0.25 'cubic lengths'.
% 
% Looking just above the bar codes on the items he finds their weights and 
% volumes. He digs out his recent copy of a financial paper and gets the 
% value of each item.
%
% Item	                 Explanation	                Value (each)   weight	Volume (each)
% --------------------------------------------------------------------------------------------
% panacea (vials of)	Incredible healing properties	3000           0.3	0.025
% ichor (ampules of)	Vampires blood	                1800           0.2	0.015
% gold (bars)	        Shiney shiney	                2500           2.0	0.002
% Knapsack	        For the carrying of	        -              <= 25	<=0.25 
%
% He can only take whole units of any item, but there is much more of 
% any item than he could ever carry
%
% How many of each item does he take to maximise the value of items 
% he is carrying away with him?
%
% Note: There are four solutions that maximise the value taken. Only one need be given. 
% """

% Since it's implemented as a MIP problem, not all solvers can handle this.
% The only solver I know of that can show all 4 solutions is ECLiPSe/ic.
% 

% 
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc/
%


int: n = 3;
array[1..n] of float: value;
array[1..n] of float: weight;
array[1..n] of float: volume;

array[1..n] of var int: x;

var float: total_value = sum(i in 1..n) (int2float(x[i])*value[i]);
var float: total_weight = sum(i in 1..n) (int2float(x[i])*weight[i]);
var float: total_volume = sum(i in 1..n) (int2float(x[i])*volume[i]);

% solve maximize total_value;
solve satisfy;

constraint
   total_weight <= 25.0
   /\
   total_volume <= 0.25
   /\
   forall(i in 1..n) ( 
        x[i] >= 0
    ) 

   % for all solutions
   /\ total_value >= 54500.0
;

output [
   "total_value: " ++ show(total_value) ++ "\n" ++
   "total_weight: " ++ show(total_weight) ++ "\n" ++
   "total_volume: " ++ show(total_volume) ++ "\n"
] ++ 
[
  show(i) ++ ": " ++ show(x[i]) ++ "\n"
  | i in 1..n
] 
++ ["\n"];

%
% data
%
value  = [3000.0, 1800.0, 2500.0  ];
weight = [   0.3,    0.2,    2.0  ];
volume = [   0.025,  0.015,  0.002];