Expert: Scott A Wilson - 2/5/2010

Question
QUESTION: Hi,
Recently,I read some articles regarding the coin exchange problem and its solution. All the solutions using dynamic programing assume that one coin has value 1(in order to guarantee that there is a solution).
My question is this: Can I use the same algorithm without the assumption (coin value 1)that will inform me if there isn't a solution to the problem (if that turns out to be the case)?
In other words, given a natural number N, and M different coin denominations (but not necessarily coin with the value 1), all I wont to know is: can this number (N) be represented as a linear combination of these coins.
Hope I have been clear enough.
Regards,
Samir

ANSWER: To be sure and get every value, a coin with a value 1 is needed.
In the US, a note of currency is worth 100 cents.

Now if you had a coin worth 2 and a coin worth 3, every number in the list could be found to be a sum of N 2 cent and M 3 cent coins, but what if something was only 1 cent? I couldn't be done unless you gave them 3 cents and they returned 2 cents, but giving change is not allowed in this problem.


---------- FOLLOW-UP ----------

QUESTION: I get your point completely, but I'm afraid I failed to explain what was mine.
So, let me try this way: Can I use the same dynamic programing algorithm (used for solving the coin exchange problem) to answer a Yes/No question to wether a certain number N can be expressed as a linear combination of some subset of M coins (all with different denominations but none with a value 1).
Sorry for troubling you again,
Samir

Answer
As far as dynamic programming is concerned, the answer is yes.
I believe it would take the large coin and get as many as it could.
It would then take the next largest coin and add them on.

I believe that the change machines in most stores use this approach when dispensing change.
The only thing to check for is if the macine is out of any of the coins.
The simple ones are 1 dime is 2 nickecls, 1 dime is 10 pennies, 1 nickel is 5 pennies.
Quarters get a bit tricky, for 30 cents is either 1 quareter and 1 nickel, or 3 dimes.

I'm sure that they have been programmed to give as few coins as possible,
yet sometimes I wonder if they have been instructed to gives3 dimes
if they have a lot of dimes for 30 cents as opposed to a quarter and a nickel.

Since the coin machines do it, it must have been humanly solved and programmed.