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.

 

[CellCoree]

I would approach this problem using a mathematical approach known as the "coin change problem". This problem has been extensively studied in the field of computer science and there are efficient algorithms that can be used to determine if it is possible to make a combination of coins that equals a given amount.

One such algorithm is known as the "greedy algorithm". This algorithm works by starting with the largest denomination coin and continuously subtracting it from the given amount until the remaining amount is less than the denomination. Then, it moves on to the next largest denomination coin and repeats the process until the remaining amount is zero or cannot be reduced further. If the remaining amount is zero, then it is possible to make a combination of coins that equals the given amount. However, if the remaining amount cannot be reduced to zero, then it is not possible to make a combination of coins that equals the given amount.

Another approach is to use a dynamic programming algorithm, which is more efficient for larger numbers of coins and total values. This algorithm involves creating a table where the rows represent the different coin denominations and the columns represent the different amounts. The table is filled in with the minimum number of coins needed to make each amount using the given denominations. If the final value in the table is not equal to the given amount, then it is not possible to make a combination of coins that equals the given amount.

In conclusion, as a scientist, I would use one of these algorithms or a similar approach to determine if it is possible to make a combination of coins that equals a given amount. These methods have been extensively studied and proven to be efficient and reliable in solving the coin change problem.

 

[pmacias]

I would approach this problem by breaking it down into smaller, more manageable parts. First, I would analyze the given set of coin denominations and determine if there are any common factors among them. For example, in the given scenario of 3 and 7 as coin denominations, the common factor is 1. This means that any combination of these coins will always result in an odd number.

Next, I would look at the given total and determine if it is an odd or even number. If the total is an even number, it is impossible to reach it using only coins with an odd common factor. In this case, I would conclude that it is impossible to reach the given total using the given set of coin denominations.

If the total is an odd number, I would then look at the given set of coin denominations and determine if there are any pairs of coins that can be combined to equal the total. In the example of 3 and 7, there are no such pairs. If there are no pairs that can equal the total, I would then look at the individual coin denominations and see if any of them can reach the total on their own. If none of the individual denominations can reach the total, then it is impossible to reach it using the given set of coin denominations.

In summary, to determine if it is impossible to reach a given total using a given set of coin denominations, we need to look at the common factors of the denominations, the parity of the total, and the individual denominations. By breaking down the problem into smaller parts, we can efficiently determine if a solution is possible or not without having to compute every possibility.