## Coin Denomination Problem !

I was asked to solve the coin denomination problem in an Interview. The problem statement is: Given an amount of money, and some coins that are used in some country ( which will definitely include at-least 1 coin of worth 1), you have to find the minimum number of coins which will be used to convert the amount of money in coins. I came up with 3 solutions ( greedy algorithm which is trivial ), recursive which is tough but costly and finally a Dynamic Programming solution. I coded the algorithm in C# which is pasted below, this code will print the minimum number of coins that will be used, but the not exactly those coins which are being used in the solution, for that very purpose we have to store some addictional information, but doing that is not that much of a tough task, so enjoy the C# code

//***************** this is portion of code

int money = 9; // set any amount of money here

int [] maxcoins = new int [money + 1];

int [] coins = { 1 , 4 , 5}; // set any values here

for( int i=0; i < maxcoins.Length; i++)

maxcoins[i] = 10000; //this value should infact be very large

maxcoins[0] = 0;

for(int i = 1; i <= money; i++)

{

for( int j=0 ; j < coins.Length; j++)

{

if( i >= coins[i])

if( (maxcoins[i – coins[j]] + 1) < maxcoins[i])

maxcoins[i] = maxcoins[ i – coins[j]] + 1;

}

}

Console.WriteLine( maxcoins[money + 1]);

I will explain the logic later. 😉

Haroon

Hi Haroon,

I am facing the same difficult problem for a problem set. I have tried many times to formulate my own code but I can’t seem to get the correct result.

Can you please, either: explain to me the logic, or: send me a copy of your code.

I will appreciate it very much, as this is an urgent problem.

Thanks in advance.

Google preved rodnoy!

apcservicder

I would like to know the logic or the code…i have the same problem but i have to find the number of minimum coins for a euro…the coins are 50, 20, 10, 5, 2, and 1 cent…..a euro has 100 cents….Can you help me please?

Let’s say the denominations are 1, 2, 5, 8, 10. You need to find 24. Your algorithm will produce {10, 10, 2, 2} but the optimal solution is {8, 8, 8}. Any thoughts on this?

I think this problem has to be solved using 2Diamensional Dynamic Programming. http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

http://www.seeingwithc.org/topic1html.html

The solution that you gave is exactly the greedy algorithm, so I went ahead and wrote up what it should look like using dynamic programming in python.. 🙂

http://cmonkeyfreeware.blogspot.com/2008/02/coin-denomination-problem.html

Cmonkey, why do you say this is greedy?

I didn’t trace either yours or Haroon’s. But both your algorithms look the same to me (structurally) if we replace your ‘CheckLeast’ with a for-loop. Both look DP to me too.

I think this problem is quite simple.

Let v be the value of currency I am interested in.

Let C be the set of all coins I have.

Let V (c), for c \in C, return the value of coin c.

Then, define function f, taking a decimal, to be the minimum number of coins required to encode a particular value.

f (v) = 1 + min_{c \in C} f (v – V (c))

With base cases,

f (0) = 0

f (-1 .. – \infty) = \infty

For the above example with 24, this will return 3.

f (8) = 1 + f (0) = 1

f (16) = 1 + f (8) = 2

f (24) = 1 + f (16) = 3

If we are interested in the actual coins used, then we just need to have a data structure store the coins that generate the minimum in the function above.

This is called a dynamic programming algorithm because for a given call to f (y), with value y, if we have computed this value before then we simply return the precomputed value instead of doing the recursion anew.

Kind regards,

Owen.

i think there is a small error in the code. might be some typing mistake

“if( i >= coins[i])”

it should be “if( i >= coins[j])”

i think this was why andrew was getting wrong answer

Waqi says:

December 17th, 2009 9:30 am

Hi Guys,

My Name is Waqi and i collect coins. Checkout my collection. But i haven’t uploaded all of my collection yet. I got around more then 30,000 coins. So its not easy to upload all, it will take a bit time.

http://www.omnicoin.com/?collection=WAQIAHMED

Waqi

waqiahmed@hotmail.com

I dont think ur solution is working

static void Main(string[] args)

{

double [] denom = new double[6] {100,50,10,5,1,0.50};

double [] coins = new double[6];

double result;

double amt = Convert.ToDouble(Console.ReadLine());

for (int i = 0; i < denom.Length ; i++)

{

result = amt / denom[i] ;

amt = amt % denom[i];

coins[i] = Math.Truncate(result);

}

for (int j = 0; j = 1)

{

Console.WriteLine(“${0} = {1}”,denom[j],coins[j]);

}

}

Console.Read();

}