[algogeeks] Re: Cashbox withdrawal

[kestrel]

Yes, you are right but this is not an efficient solution. It runs in
O(n*S) time and S in my case is  sufficiently large.
 What I have noticed that the greedy algorithm works indeed in most of
the cases. If there is at least one single number of each denomination,
the greedy algorithm will work correctly. I couldn't reach a proof of
this yet (can you? ) But I have verified that my using generating
function approach and writing some mathematica programs to do the
calculations.