chickadee » coin-change » coin-change

target

The value that the solution must add up to.

denominations

The list of available denominations, and respective counts (i.e., upper closed limit).

Returns two values: the solution (or #f), and the memoization table.

Solves the coin change problem, taking into account a given finite limit of coins of each denomination, using a "dumb" greedy algorithm. This doesn't necessarily result in the minimum number of coins for non-canonical sets of denominations, but is in practice not far from it, and is simple to implement. Uses a couple of simple checks to fail early in certain scenarios, and a memoization table, from target to denomination to solution (this works because of the greedy nature). The recursive level will be at most the number of denominations.

Mathematically speaking, given target T, denominations di, and counts ci, it computes the coefficients si of the following linear equation, such that 0 <= si <= ci: T = (sum (* si di))

(coin-change 765 '((50 . 123) (10 . 456) (5 . 789)))
;=> ((50 . 15) (10 . 1) (5 . 1))
;   ((5 (5)) (15 (10) (5 . 1)) (765 (50) (10 . 1) (5 . 1)))

This is NOT the solutions counting algorithm!