algorithm Greedy Algorithms Change-making problem
Example
Given a money system, is it possible to give an amount of coins and how to find a minimal set of coins corresponding to this amount.
Canonical money systems. For some money system, like the ones we use in the real life, the "intuitive" solution works perfectly. For example, if the different euro coins and bills (excluding cents) are 1€, 2€, 5€, 10€, giving the highest coin or bill until we reach the amount and repeating this procedure will lead to the minimal set of coins.
We can do that recursively with OCaml :
(* assuming the money system is sorted in decreasing order *)
let change_make money_system amount =
let rec loop given amount =
if amount = 0 then given
else
(* we find the first value smaller or equal to the remaining amount *)
let coin = List.find ((>=) amount) money_system in
loop (coin::given) (amount - coin)
in loop [] amount
These systems are made so that change-making is easy. The problem gets harder when it comes to arbitrary money system.
General case. How to give 99€ with coins of 10€, 7€ and 5€? Here, giving coins of 10€ until we are left with 9€ leads obviously to no solution. Worse than that a solution may not exist. This problem is in fact np-hard, but acceptable solutions mixing greediness and memoization exist. The idea is to explore all the possibilies and pick the one with the minimal number of coins.
To give an amount X > 0, we choose a piece P in the money system, and then solve the sub-problem corresponding to X-P. We try this for all the pieces of the system. The solution, if it exists, is then the smallest path that led to 0.
Here an OCaml recursive function corresponding to this method. It returns None, if no solution exists.
(* option utilities *)
let optmin x y =
match x,y with
| None,a | a,None -> a
| Some x, Some y-> Some (min x y)
let optsucc = function
| Some x -> Some (x+1)
| None -> None
(* Change-making problem*)
let change_make money_system amount =
let rec loop n =
let onepiece acc piece =
match n - piece with
| 0 -> (*problem solved with one coin*)
Some 1
| x -> if x < 0 then
(*we don't reach 0, we discard this solution*)
None
else
(*we search the smallest path different to None with the remaining pieces*)
optmin (optsucc (loop x)) acc
in
(*we call onepiece forall the pieces*)
List.fold_left onepiece None money_system
in loop amount
Note: We can remark that this procedure may compute several times the change set for the same value. In practice, using memoization to avoid these repetitions leads to faster (way faster) results.
