Author |
Topic: coins and change (Read 6773 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
coins and change
« on: Feb 5th, 2012, 9:07am » |
 Quote  Modify
|
You have coins with different denominations and you have limited number of each denominations (some maybe zero), how will you determine if you can supply the given change.
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: coins and change
« Reply #1 on: Feb 5th, 2012, 11:23am » |
Quote Modify
|
I think it depends on the denominations whether a greedy approach will work; but that'd be one thing to try.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: coins and change
« Reply #2 on: Sep 22nd, 2012, 2:50am » |
Quote Modify
|
Can we model it as DP?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: coins and change
« Reply #3 on: Jul 20th, 2013, 1:07am » |
Quote Modify
|
on Sep 22nd, 2012, 2:50am, R wrote:
Dynamic programming would be awkward in this case, because there would be multiple ways of getting to each amount.
I would use an integer programming library: unless the problem was extraordinarily large, it would answer this question in a snap.
http://en.wikipedia.org/wiki/Change-making_problem
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print