Algorithm possible amounts (over)paid for a specific price, based on denominations
- by Wrikken
In a current project, people can order goods delivered to their door and choose 'pay on delivery' as a payment option. To make sure the delivery guy has enough change customers are asked to input the amount they will pay (e.g. delivery is 48,13, they will pay with 60,- (3*20,-)). Now, if it were up to me I'd make it a free field, but apparantly higher-ups have decided is should be a selection based on available denominations, without giving amounts that would result in a set of denominations which could be smaller.
Example:
denominations = [1,2,5,10,20,50]
price = 78.12
possibilities:
79 (multitude of options),
80 (e.g. 4*20)
90 (e.g. 50+2*20)
100 (2*50)
It's international, so the denominations could change, and the algorithm should be based on that list.
The closest I have come which seems to work is this:
for all denominations in reversed order (large=>small)
add ceil(price/denomination) * denomination to possibles
baseprice = floor(price/denomination) * denomination;
for all smaller denominations as subdenomination in reversed order
add baseprice + (ceil((price - baseprice) / subdenomination) * subdenomination) to possibles
end for
end for
remove doubles
sort
Is seems to work, but this has emerged after wildly trying all kinds of compact algorithms, and I cannot defend why it works, which could lead to some edge-case / new countries getting wrong options, and it does generate some serious amounts of doubles.
As this is probably not a new problem, and Google et al. could not provide me with an answer save for loads of pages calculating how to make exact change, I thought I'd ask SO: have you solved this problem before? Which algorithm? Any proof it will always work?
