The Coin Problem

 Developed by Hardeep Singh Copyright © Hardeep Singh, 2000 - 2008 EMail 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
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 *)
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;   (* No coins are reqd to construct amount 0 *)
coin:=0;
FOR i:=1 TO amt DO
BEGIN
min:=minnum[i-d]; (* 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` & `coin` 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. 