## Coin Change, Part 1

### May 17, 2013

The counting function loops through the coins in *xs*, and for each coin loops from the value of the coin to *n* adding the count for the current target less the current coin:

`(define (count xs n)`

(let ((cs (make-vector (+ n 1) 0)))

(vector-set! cs 0 1)

(do ((xs xs (cdr xs)))

((null? xs) (vector-ref cs n))

(do ((x (car xs) (+ x 1))) ((< n x))

(vector-set! cs x (+ (vector-ref cs x)

(vector-ref cs (- x (car xs)))))))))

The enumerating function is the same, except that it keeps list of coins instead of counts:

`(define (coins xs n)`

(let ((cs (make-vector (+ n 1) (list))))

(vector-set! cs 0 (list (list)))

(do ((xs xs (cdr xs)))

((null? xs) (vector-ref cs n))

(do ((i (car xs) (+ i 1))) ((< n i))

(vector-set! cs i

(append (vector-ref cs i)

(map (lambda (zs) (cons (car xs) zs))

(vector-ref cs (- i (car xs))))))))))

The dynamic programming aspect of the solution is obvious, as both functions use the vector *cs* to keep solutions to sub-problems, finally returning the value in the last element of the vector.

Here are two examples:

`> (count '(1 5 10 25) 40)`

31

> (coins '(1 5 10 25) 40)

((1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1)

(5 5 5 5 5 5 5 1 1 1 1 1)

(5 5 5 5 5 5 5 5)

(10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(10 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(10 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(10 5 5 5 5 1 1 1 1 1 1 1 1 1 1)

(10 5 5 5 5 5 1 1 1 1 1)

(10 5 5 5 5 5 5)

(10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(10 10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(10 10 5 5 1 1 1 1 1 1 1 1 1 1)

(10 10 5 5 5 1 1 1 1 1)

(10 10 5 5 5 5)

(10 10 10 1 1 1 1 1 1 1 1 1 1)

(10 10 10 5 1 1 1 1 1)

(10 10 10 5 5)

(10 10 10 10)

(25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

(25 5 1 1 1 1 1 1 1 1 1 1)

(25 5 5 1 1 1 1 1)

(25 5 5 5)

(25 10 1 1 1 1 1)

(25 10 5))

You can run the program at http://programmingpraxis.codepad.org/RekApsRy.

In a future exercise we will see a variant on the coin change problem where the task is to determine the smallest set of coins that sum to a particular target, without first enumerating all the possibilities.

[…] today’s Programming Praxis exercise, our goal is to list all of the ways in which a target amount can be […]

My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/17/programming-praxis-coin-change-part-1/ for a version with comments):

Here is a Ruby program with both functions

coin-change1 output

hosted with ❤ by GitHub

coin-change1.rb

hosted with ❤ by GitHub

Here is the output:

[…] This post presents C# solutions to a coin change problem as described in https://programmingpraxis.com/2013/05/17/coin-change-part-1. […]

I have done this exercise using a simple method: I divide the total (T) by the first coin (C1). I take the integer part of this division (n1=T//c1). n1 represents the maximum number of possiblities of having c1 in any combinaison. After that, I do the same process for finding the total minus 0, 1,…, n1*c1 now using just the new set (C2, C3, C4).

Here is the program in Python, and it works well: the result is outputed very fast.

c1=25

c2=10

c3=29

c4=3

T=40

C=[]

for i in range(0, (T//c1)+1):

if T-(i

c1)==0:c1)//c2)+1):C.append([i,0,0,0])

continue

for j in range(0, ((T-i

if T-i

c1-jc2==0:C.append([i,j,0,0])

continue

for w in range(0, ((T-i

c1-jc2)//c3)+1):if (T-i

c1-jc2-wc3)%c4 == 0:c1-jC.append([i,j,w,(T-i

c2-wc3)//c4])for i in C:

print(i)

print(len(C))

[…] solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be […]