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 didj
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=0) AND (minnum[i-d[j]]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.
<<>> 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