% 
% Yet another coin problem in MiniZinc.
% 
% From 
% http://forum.openopt.org/viewtopic.php?id=5
% """
% In my pocket I have £41.58 which is made up of different denominations of coins. 
% There is exactly the same number of each coin. What is the minimum number of coins 
% I have, and what are they? (Britain has 8 commonly used coins, and in GBP their 
% values are: 0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1, 2).
% """

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

int: n = 8;
array[1..n] of int: denom = [1, 2, 5, 10, 20, 50, 100, 200]; % in cents
int: s = 4158; % 41.58
array[1..n] of var int: x :: is_output;
var int: num_coins :: is_output = sum(i in 1..n) (x[i]);

solve :: int_search(x, smallest, indomain_min, complete) minimize num_coins;
% solve :: int_search(x, smallest, indomain_min, complete) satisfy;

constraint
%   s = 4158
%   /\
   sum(i in 1..n) (x[i]*denom[i]) = s
   /\
   forall(i in 1..n) (
      x[i] >= 0
      /\
      x[i] <= s
   )
   /\
   forall(i, j in 1..n) (
     x[i] = x[j] 
     \/ 
     x[i] = 0 
     \/
     x[j] = 0
   )
;