Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# isaiah-perumalla/change.fs

Last active Dec 20, 2015
make change algorithm. compute change with using minimum number of coins
 [] 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

) xs = List.filter (fun (coin, _) -> x >= coin) xs let num_coins (coin:int

, qty:int) (amt:int

) = 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

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

, 10); (3

, 3); (2

, 3);(1

, 0)] mkchange coins_available 6

;; (* esoteric denominations *) let coins_available = [(11

, 20); (7

, 20); (3

,4)] mkchange coins_available 112

;; (* 11p x 9 and 7p x1 and 3p x 2 *) (* optimal change *) let coins_available = [(10

, 20); (7

, 10); (1

,10)] mkchange coins_available 24

;; (* 10p x 1 and 7p x2 *) (* large denominations and amounts *) let coins_available = [(10000

, 20); (5000

, 20); (2000

,40);(1000

,40);(500

,40); (200

,40);(100

,40); (50

,40); (20

,40);(2

,4000);(1

,40000)] mkchange coins_available 114000

;; (*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 *)

to join this conversation on GitHub. Already have an account? Sign in to comment