blob: 1df83e93d0d728f730a40e458e80a5eb23331f37 (
plain)
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
|
(define-module (cs)
#:export (cs))
(define (cs limit denominations)
"Given DENOMINATIONS of available coins,
calculates the total number of different coins
which combine to LIMIT worth."
(define (count-coins coins ut)
"Calculates the total of combinations with
the lowest coin denomination first, then recursively
adds coins of increasing worth, indexing previous results.
This is the dynamic programming approach."
(if (null? coins)
ut
(let ((coin (car coins)))
(for-each (lambda (a)
(vector-set! ut a (+ (vector-ref ut a)
(vector-ref ut (- a coin)))))
(iota (- (1+ limit) coin) coin 1))
(count-coins (cdr coins) ut))))
(let ((ut (make-vector (1+ limit) 0)))
(vector-set! ut 0 1)
(cdr (vector->list (count-coins
(filter (lambda (x) (>= limit x)) denominations)
ut)))))
|
