The Coin Problem

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.