Re: Cashbox withdrawal
- From: LC Killingbeck <NOTlynn.killingbeck@xxxxxxxxxxxxxxxx>
- Date: Wed, 14 Dec 2005 02:30:41 GMT
"kestrel" <youssef.mohammed@xxxxxxxxx> wrote in
news:1134520755.051440.283750@xxxxxxxxxxxxxxxxxxxxxxxxxxxx:
> Hmmm, it talks about another problem. In my case, I have limited amount
> of each denominations, and my goal to find whether I can change the
> amount I have or not. The change-making problem in the literature talks
> about find the minimal number of coins to change some amount assuming
> infitine number of coins for each denomination.
> Someone suggested that I can use the generating function for this as
> follow :
> Here's an example. Suppose I have 50 nickels, 20
> dimes, and 100 quarters. Consider the following polynomial:
> "
> (1 + x^5 + x^10 + ... + x^250) * (1 + x^10 + x^20 + ... + x^400)
> * (1 + x^25 + x^50 + ... + x^2500)
>
> The first observation is that if you multiply everything out, the
> coefficient of x^n is the number of ways of making n out of these
> coins.
> In particular, if x^n doesn't appear at all, then n can't be made out
> of
> these coins.
>
> The second observation is that by using the formula for a geometric
> series,
> we can rewrite the product as
>
> (1 - x^255)*(1 - x^410)*(1 - x^2525) / (1 - x^5)*(1 - x^10)*(1 - x^25)
>
> You can then try a partial fraction decomposition of this rational
> function,
> together with textbook formulas for Taylor expansion. "
>
> but I think this is too expensive to compute in a software program
>
Perhaps exercise 21 in section 7 of "Concrete Mathematics" by Graham,
Knuth and Patashnik would help you. I have not worked through that
section yet, but it sounds similar (albeit with just two denominations).
"A robber breaks into a bank and demands $500 in tens and twenties. He
also demands to know the number of ways in which the cashier can give
him the money. ..." Cheating by looking at the answer in the back of the
book, one expression is simply floor(50/2)+1=26.
Sorry if this duplicates some other response. I've missed most of the
thread.
Lynn Killingbeck
.
- References:
- Cashbox withdrawal
- From: kestrel
- Re: Cashbox withdrawal
- From: Don Reble
- Re: Cashbox withdrawal
- From: kestrel
- Cashbox withdrawal
- Prev by Date: Re: Question about markov chains
- Next by Date: Re: Why to accept that the present set of arithmetical axioms are sufficient?
- Previous by thread: Re: Cashbox withdrawal
- Next by thread: Does the simultaneous gradient method converge to the saddle point?
- Index(es):
Relevant Pages
|
