1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
(***********************************************************************)
(* *)
(* FaCiLe *)
(* A Functional Constraint Library *)
(* *)
(* Nicolas Barnier, Pascal Brisset, LOG, CENA *)
(* *)
(* Copyright 2004 CENA. All rights reserved. This file is distributed *)
(* under the terms of the GNU Lesser General Public License. *)
(***********************************************************************)
(* $Id: coins.ml,v 1.13 2004/09/07 09:24:43 barnier Exp $ *)
(*
Which coins do you need to give back change for any amount between
0 and [max], using coins from [values].
*)
open Facile
open Easy
let coins values max =
let domains = Array.map (fun v -> Domain.interval 0 (max / v)) values in
let gen_vars () = Array.map (fun d -> Fd.create d) domains in
(* The solution *)
let nb_min_coins = gen_vars () in
let mat =
Array.init max
(fun i ->
(* coins needed to give back i *)
let nb_coins = gen_vars () in
Cstr.post (Arith.scalprod_fd values nb_coins =~ i2e i);
for j = 0 to Array.length nb_coins - 1 do
let nbpj = nb_coins.(j)
and nbmpj = nb_min_coins.(j) in
Cstr.post (fd2e nbpj <=~ fd2e nbmpj)
done;
nb_coins) in
(* Cost: nb of coins *)
let cost = Arith.e2fd (Arith.sum_fd nb_min_coins) in
let cost = Fd.interval 0 max in
Cstr.post (fd2e cost =~ Arith.sum_fd nb_min_coins);
(* Search goal *)
let goal =
Goals.Array.forall Goals.Array.labeling mat
&&~ Goals.Array.labeling nb_min_coins in
(* Searching for the best solution *)
let best = ref [||] in
ignore
(Goals.solve
(Goals.minimize goal cost
(fun c ->
Printf.printf "%d found\n" c; flush stdout;
best := Array.map Fd.int_value nb_min_coins)));
match !best with
[||] -> prerr_endline "No solution"
| sol -> Array.iter (fun x -> Printf.printf "%d " x) sol; print_newline ();;
let _ =
coins [|1;2;5;10;20|] 100;;
|
