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?