Re: Cashbox withdrawal
- From: israel@xxxxxxxxxxx (Robert Israel)
- Date: 14 Dec 2005 06:26:11 GMT
In article <1134526498.189971.176260@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
kestrel <youssef.mohammed@xxxxxxxxx> wrote:
>:( this is really interesting but it is not helping me anymore. In my
>problem I do have limits on the number of coins to use as i described
>in my first post. And my only concern is to say yes I can change this
>amount or not.
OK, suppose you have n_j of denomination d_j, j = 1..k.
Let S_0 = {0}, and for j from 1 to k let
S_j = S_{j-1} + {i d_j: i=0..n_j}
(where for two sets A and B, A + B = {a + b: a in A, b in B}).
Then S_k is the set of all amounts you can make with these coins.
Alternatively, let P(x) = product_{j=1}^k (1 + x^d_j)^n_j. There is
a way to make y with these coins if and only if the coefficient of
x^y in P(x) is nonzero. I think the efficient way to compute the
coefficients (and thus determine which are zero) is using a Fast Fourier
Transform.
Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.
- References:
- Cashbox withdrawal
- From: kestrel
- Re: Cashbox withdrawal
- From: kestrel
- Re: Cashbox withdrawal
- From: Robert Israel
- Re: Cashbox withdrawal
- From: kestrel
- Cashbox withdrawal
- Prev by Date: Complex measures and variation
- Next by Date: Re: what "REALLY" is derivative?
- Previous by thread: Re: Cashbox withdrawal
- Next by thread: Re: Cashbox withdrawal
- Index(es):
Relevant Pages
|
