__The Coin Problem__

Developed by Hardeep Singh | |

Copyright | © Hardeep Singh, 2000 - 2008 |

seeingwithc@hotmail.com | |

Website | www.seeingwithc.org |

All rights reserved. | |

The code may not be used commercially without permission. | |

The code does not come with any warranties, explicit or implied. | |

The code cannot be distributed without this header. |

Let us say we have an amount we have to pay someone: say $97. The given currency has notes worth $1, $5, $10 and $50. Now, what is the minimum number of currency notes with which the amount can be made? In this case, its eight: two $1 notes, a $5 note, four $10 notes and a $50 notes - eight in all.

If a computer had to solve the same problem, how would it do it? Let us see below. ‘Denomination’ refers to the list of available currency notes: $1, $5, $10 and $50 in this case - each note is a denomination.

** Problem:** We are given a
set of denominations

`d1`

,`d2`

,`d3`

,...,`dn`

in increasing order. (Without
loss of generality) we assume also that `d1`

=1 (that is, there is always a $1 note,
and that is the first denomination) so that it is always
possible to produce all amounts from the given denominations. We
are also given an amount of money `amt`

. We must use a minimum
number of coins (or currency notes) of the given denominations to produce `amt`

.Solution #1: __The naive approach (Greedy
algorithm)__

The easiest way to approach the solution is to
divide `amt`

by the coin with the largest denomination (`dn`

). Let us say
the number is `k1`

. Now, whatever remains must be divided again by
`dn-1`

and so on. Thus `k1`

+`k2`

+...+`kn`

will be the result we seek, the minimum
number of coins with which the amount can be made. This approach
is known as the Greedy approach to problem solving. The following
procedure solves the problem in this fashion:

PROCEDURE findcoins1(d:denom; n,amt:integer; VAR c:counts); VAR i:integer; BEGIN i:=n; (* start with the largest coin *) WHILE amt>0 DO BEGIN c[i]:=trunc(amt/d[i]); (* get the number of coins required *) amt:=amt-c[i]*d[i]; (* this amount remains *) i:=i-1; END; WHILE i>=1 DO (* make the numbers of other coins 0 *) BEGIN c[i]:=0; i:=i-1; END; END;

Both `denom`

and `counts`

are declared to be arrays
of integers [1..1000]. Although this method works for the Indian currency,
consider the set of denominations {1,10,30,40}. Also consider an
amount 60. Based on this approach, we will divide the amount 60, first by
40 (because that is the largest denomination) to get 1 coin, then
the remainder 20 by 30, to get none. Again, 20 will be divided by
10 to get 2 coins. Thus the problem will be solved by using 2
denomination 20 coins and a denomination 40 coin. However, we can
solve the problem by using only 2 coins of denomination 30. Hence
the algorithm is not optimal.

This problem can arise only for certain
denomination sets. If the set has at least one set of denominations
`(di,dj)`

(`j`

>i) such that
`di`

<`dj`

and `2*di`

>`dj`

then it can have
some values of amt for which the above algorithm fails.

Always dividing first by the largest coin gets us an optimal number of coins in most but not all cases. Had we divided first by the coin of denomination 30 first, we would have got the optimal result. However, how to decide which coin to use first in which case?

There is no uniform way to answer this question, hence this approach must be discarded. For the denomination set given above and an amount 70, dividing by 30 first solves the problem in 3 coins(30,30,10) whereas it can be solved only in 2 coins(40,30) if we divide by 40 first.

Solution #2: __Recursive approach__

The other way to solve the problem is by
splitting the amount into smaller amounts and then producing
those smaller amounts using the minimum number of coins. Let us
consider amount 60 and denomination set {1,10,30,40}. The amount
can be written as (59+1),(50+10),(30+30) or (20+40). Consider a
function `howmany(amt)`

that finds the minimum number of coins
required to make an amount `amt`

. If `howmany(amt)`

is called, it
finds the minimum of `howmany(59)`

, `howmany(50)`

, `howmany(30)`

and
`howmany(20)`

, adds 1 to the result and gives this as the value of
the function. This function is given below:

FUNCTION howmany(d:denom; n,amt:integer; VAR w:integer):integer; VAR i,min,t,value,v:integer; flag,out:boolean; BEGIN flag:=false; (* atleast one denomination found *) out:=false; (* the sum has been constructed *) i:=n; (* start with the largest coin *) REPEAT IF (amt-d[i]>0) THEN (* can d[i] be used? *) BEGIN t:=howmany(d,n,amt-d[i],v); (* get the number of coins if d[i] is used *) IF (NOT(flag)) OR (t<min-1) THEN (* accept if smaller than earlier values *) BEGIN value:=i; (* store the value and number of coins *) min:=t+1; flag:=true; (* flag that a denomination is found *) END; END ELSE IF (amt-d[i]=0) THEN (* if the amount has been made *) BEGIN value:=i; min:=1; flag:=TRUE; out:=true; (* terminate looping *) END; i:=i-1; UNTIL (i=0) OR (out); w:=value; howmany:=min; END;

All that the program has to do is to find the
numbers of coins based on the results of `howmany`

:

PROCEDURE findcoins2(d:denom; n,amt:integer; VAR c:counts); VAR i,j,m:integer; BEGIN FOR i:=1 TO n DO (* initialise to zero *) c[i]:=0; REPEAT j:=howmany(d,n,amt,m); (* find out howmany coins & which *) c[m]:=c[m]+1; (* increment the number of used coin *) amt:=amt-d[m]; (* calculate amount left *) UNTIL (amt=0); (* until amt=0 *) END;

This approach, although flawless, takes a lot
of time. Consider {1,3,10,30,75} and `amt`

=45. It
took 20 seconds flat on my Pentium II 350 Mhz system.

The reason it took so much time is that `howmany`

is
calculated for the same amount more than once. For instance, in the
above example, `howmany(20)`

& `howmany(30)`

are
calculated once during calculation of `howmany(60)`

and `howmany(20)`

is
calculated again during calculation of `howmany(30)`

. In short, the same
calculation is being carried out more than once. Let us see
how things can be improved.

Solution #2: __Dynamic Programming__

A way to speed things up is
by storing values of `howmany(amt)`

that have been calculated in a
table and reusing them later. This method of programming is
called Dynamic Programming (the word dynamic, as used here, has
nothing to do with memory allocation).

Dynamic programming therefore is a top-down approach: split the larger problem into smaller ones, solve the smaller ones (putting away the solution for each smaller problem somewhere so that it can be used again in case needed later), and combine to produce the solution to the larger problem. We did the same in the previous solution, except that we did not put away solutions for reuse - we ‘recalculated’ on demand!

The following procedure demonstrates this:

PROCEDURE findcoins3(d:denom; n,amt:integer; VAR c:counts); VAR minnum,coin:ARRAY[0..1000] of integer; i,j,min,denomination:integer; BEGIN minnum[0]:=0; (* No coins are reqd to construct amount 0 *) coin[0]:=0; FOR i:=1 TO amt DO BEGIN min:=minnum[i-d[1]]; (* Consider 1st denomination as lowest coin making *) denomination:=1; FOR j:=2 TO n DO (* Go through other denominations *) IF (i-d[j]>=0) AND (minnum[i-d[j]]<min) THEN (* If fewer coins needed *) BEGIN min:=minnum[i-d[j]]; (* Store this denomination *) denomination:=j; END; minnum[i]:=min+1; (* Store the minimum denomination *) coin[i]:=denomination; END; FOR i:=1 TO n DO (* Initialise c to zeros *) c[i]:=0; WHILE (amt>0) DO BEGIN c[coin[amt]]:=c[coin[amt]]+1; (* Calculate & store the number of coins of each den. *) amt:=amt-d[coin[amt]]; END; END;

The procedure uses two local arrays. The array
`minnum`

stores in each cell, the minimum number of coins required
to construct the amount denoted by the index of the cell (that is
`minnum[i]`

stores the minimum number of coins required to make amount `i`

). The
array `coin`

stores the coin of largest denomination that is used
to construct the amount of the index. Thus, `minnum[0]`

& `coin[0]`

are initialised to zero. Thereafter, `minnum[i]`

& `coin[i]`

are
calculated for each `i`

from `1`

to `amt`

. The improvement in speed is
considerable. Consider again {1,3,10,30,75} and `amt`

=45. This
procedure prints the results immediately. However, this procedure
requires extra space proportional to the amount. This may not
always be possible. However, this algorithm is linear in time
whereas `findcoins2`

is exponential.

Dynamic programming is used for a lot of other problems, the popular
ones among those being word wrapping (**optimally** wrapping words on a
line to fit the margins) and ‘Duckworth-Lewis method’ used to decided
interrupted Cricket matches, for example by rain.

**Note** to any implementation using procedures defined here: all procedures accept input denominations
starting at 1 (so first denomination always 1) and in increasing order thereafter. The input needs to
be validated prior to passing to the procedures, and is the responsibility of the calling program.