The Coin Problem
----------------

Developed by Hardeep Singh.
Copyright: Hardeep Singh, 2000.
EMail    : seeingwithc@hotmail.com
Website  : 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. 

[Look at http://www.seeingwithc.org/solu1t1_1.jpg]

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. 

http://www.SeeingWithC.org