The coin denomination problem is as follows: given a number which needs to be broken down into change (such as 24$), and a set of coins (or bills) or different values (such as 10$, 8$, 5$, 2$, and 1$ bills) what is the minimum number of bills needed which will add up to make the number.
Since I am currently in the interview process with Google, I was searching for the type of questions on the internet, which is where I was first introduced to this problem. The author of one post I found (here) who described his own phone interview with Google, said that the interviewer had asked him to give a solution to this problem, which he said he had stated in another blog post (here).
But the solution that I had found was not recursive, the way it should be to demonstrate the use of dynamic programming in this case. I went ahead and wrote my own solution to this problem, in Python, a language I love (also freely available for windows).
The code:
def CoinDenomination(value,coinArray):
if value == 0:
return [0,[]]
if value < 0:
return [100000000,[]]
minval = 100000
minind = len(coinArray)+1
for i in range(len(coinArray)):
retVal = CheckLeast(value-coinArray[i],coinArray)
if temp[0] < minval:
minval = retVal[0]
minind = i
coins = retVal[1]
coins.append(coinArray[minind])
return [1 + minval,coins]
if __name__=="__main__":
retVal = CoinDenomination(24,[10,8,5,2,1])
print "Number of coins:\t",retVal[0]
print "Coins:\t\t\t",retVal[1]
It can be shown that this solution will always produce the optimal result (the least number of coins) whereas the greedy algorithm will always be faster than this solution. It is meant to demonstrate the power of dynamic programming and is a good exercise to try.
Please feel free to publish your comments and questions below, I would be happy to help clarifying this if I can.
Enjoy!
2 comments:
I'm not sure whether it is suposed to be pseudo-code, you forgot to add something, or I misunderstood something else. But your solution doesn't seem to be runnable.
Here's my solution, also in Python and using dynamic programming:
import sys
class Matrix(object):
def __init__(self, rows, cols, INFINITY=sys.maxint):
self._matrix = []
for i in range(rows):
self._matrix.append([INFINITY for j in range(cols)])
self._rows = rows
self._cols = cols
self.INFINITY = INFINITY
def __getitem__(self,x):
x,y = x
if x<0 or y<0 or x>=self._rows or y>=self._cols:
return self.INFINITY
return self._matrix[x][y]
def __setitem__(self,x, value):
x,y = x
if x<0 or y<0 or x>=self._rows or y>=self._cols:
return -1
self._matrix[x][y] = value
return self._matrix[x][y]
class Coins(object):
def __init__(self, coins, amount):
self._coins = coins
self._amount = amount
def solve(self):
n_coins = len(self._coins)
A = Matrix(n_coins, self._amount+1)
self._A = A
for i in range(n_coins):
A[i,0] = 0
for i in range(0,n_coins):
for j in range(1,self._amount+1):
A[i,j] = min(A[i-1,j], 1+A[i,j-self._coins[i]])
return A[n_coins-1,self._amount]
You can test it with something like:
>>> c = Coins([1,4,6], 8)
>>> c.solve()
>>> c._A._matrix
(sorry if blogger messes the code up, I don't know how to make it recognize whitespace)
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 < coins.Length ; j++)
{
if (coins[j] >= 1)
{
Console.WriteLine("${0} = {1}",denom[j],coins[j]);
}
}
Console.Read();
}
Post a Comment