make change algorithm. compute change with using minimum number of coins

change.fs

[<Measure>] type p 

let count ps = let rec countcs acc = function
                                     |[] -> acc
                                     |(_, qty)::xs -> (countcs (acc+qty) xs)
               in countcs 0 ps

let lessThan (x:int<p>) xs = List.filter (fun (coin, _) -> x >= coin) xs
let num_coins (coin:int<p>, qty:int) (amt:int<p>) = min qty (int(amt/coin))
let better ps bs =
                   match ps,bs with
                   |None,x | x,None -> x
                   |Some(x), Some(y) -> if ((count x) - (count y)) <= 0 then Some(x) else Some(y)

let rec choose_best chooser best  =
            function 
            |0 -> best
            |qty -> 
                let sol = better best (chooser qty) in
                if sol = best then best else  choose_best chooser sol (qty-1)

(* uses a greedy heuristic to prune search tree, and backtracks to check solution is optimal *)
let mkchange denoms amount =
    let rec mkch ps best amount =
            function
            |[] -> best
            |(coin,qty)::remainingCoins ->
                                     let qty = num_coins (coin,qty) amount in
                                     let bal = amount - coin*qty in
                                     let solution = better (Some ((coin,qty)::ps)) best in
                                     if solution = best then best
                                     elif bal = 0<p> then solution
                                     else
                                         let chg_with_coin q = mkch ((coin,q)::ps) best (amount - coin*q) (remainingCoins |> lessThan (amount-coin*q)) in
                                         let candidate = chg_with_coin qty in
                                         let optimal = choose_best chg_with_coin candidate (qty-1) in
                                         mkch ps optimal amount remainingCoins
    in mkch [] None amount (denoms |> (lessThan amount))  

(* example - 6p problem *)
let coins_available = [(5<p>, 10); (3<p>, 3); (2<p>, 3);(1<p>, 0)]
mkchange coins_available 6<p> ;;

(* esoteric denominations *)
let coins_available = [(11<p>, 20); (7<p>, 20); (3<p>,4)]
mkchange coins_available 112<p> ;; (* 11p x 9  and 7p x1 and 3p x 2 *)

(* optimal change *)
let coins_available = [(10<p>, 20); (7<p>, 10); (1<p>,10)]
mkchange coins_available 24<p> ;; (* 10p x 1  and 7p x2 *)
(* large denominations and amounts *)
let coins_available = [(10000<p>, 20); (5000<p>, 20); (2000<p>,40);(1000<p>,40);(500<p>,40); (200<p>,40);(100<p>,40); (50<p>,40); (20<p>,40);(2<p>,4000);(1<p>,40000)]
mkchange coins_available 114000<p> ;;


(*correctness proof (work in prorgess )
early stop when decreasing coin qty amounts

change of amt
D = current highest denomination
c0 = D*qty + opt_chg (amt-(D*qty))
c1 = D*(qty-1) + opt_chg (amt-  (D*(qty-1)))
.
.
.
cn = D*(qty-n) + opt_chg (amt - (D*(qty-n)))

if cn >= c_n-1 then stop
since
C_n-2 >= c_n-1 
*)