Indeed di-1 mod di = 0 is sufficient to make the greedy algorithm work,
but 50 mod 20 = 10!
oops.. 500,200 and 50,20 are values in the table.
so the algo doesnt work for this case
Hi Gene,
my Idea works - the one 3 mail...
when d1,d2, d3,...dr are sorted in non-decreasing order AND
"di-1 mod di = 0 , for all 2< i < r.".
thats why in the begining of the logic, I mentioned for this specific
problem ( as mentinoned in the table), denomincations hold the property
- "di
Your algorithm does not show how to select di. If you pick the
smallest possible denomination first, then consider S=6 with a cash box
of
2 x 1
1 x 5
The algorithm will pick both 1's and then fail because all that's left
is the 5.
If you pick the largest possble di then try S=60 with a cash box
Thank you very much for all your help.
I wish you a very Happy New Year 2006
Cyril
Cyril,
I didn't forget, but this is all I can do to help. The "solution" I
offered would probably not complete its execution within your (or my)
life time. So, that is pretty much out. The key here is to only
consider unique combinations and not permutations. Here is what other
(smarter) peop
a ^ x = b (mod p)
known a, b, p. find x.
p is prime.
