Finding Combinations of Coin Denominations for a Given Total

[rsala004]

if you are given an amount of cents, and a set of coin denominations...how can we tell if its impossible to amount to exactly the given amount of cents?

for example say we want to gather 8 units of value but only have coins with denomination 3 and 7, thus its not possible to make a combination that amounts to 8.
(3x + 7y = 8 , has no positive integer solutions)

so given any total , and any set of coin denominations (any # of coins)...how can we tell?sorry if this sounds trivial...I just can't find a method that suits my need
(ie. computing every possibility won't do the job if the number of coins and total value are large)

I could think of a way to handle the situation given only 2 coins..but any more and the problem becomes unwieldy. its likely just something simple I am not seeing

 

[Mensanator]

Can you have negative pennies?

 

[CRGreathouse]

This is called the problem of Frobinius or the coin problem. There are good methods for up to 3 coins:
http://mathworld.wolfram.com/CoinProblem.html
http://en.wikipedia.org/wiki/Coin_problem

 

[WWGD]

This is also called "the stamp problem" : if you have stamps of values p,q only, and
you want to pay for packages beyond a certain amount.

For two coins of values p,q with p,q relatively prime, there is a nice formula for the
largest number that cannot be written as ap+bq ; a,b nonnegative integers:

This highest number is (p-1)(q-1). Assume WLOG p>q . You can show this is
the smallest by producing p consecutive numbers that can be written as
ap+bq.

For more than three rel. prime numbers, this was an open problem recently, and
I think it still is. Try Googling " Postage Stamp" problem for more.