Algorithm possible amounts (over)paid for a specific price, based on denominations

Question

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?

Answer 1

Its an application of the Greedy Algorithm http://mathworld.wolfram.com/GreedyAlgorithm.html (An algorithm used to recursively construct a set of objects from the smallest possible constituent parts)

Pseudocode

list={1,2,5,10,20,50,100} (*ordered *)
while list not null
   found_answer = false
   p = ceil(price) (* assume integer denominations *)
   while not found_answer
      find_greedy (p, list) (*algorithm in the reference above*)
      p++
   remove(first(list))

EDIT> some iterations are nonsense>

list={1,2,5,10,20,50,100} (*ordered *)
p = ceil(price) (* assume integer denominations *)
while list not null
   found_answer = false
   while not found_answer
      find_greedy (p, list) (*algorithm in the reference above*)
      p++
   remove(first(list))

EDIT>

I found an improvement due to Pearson on the Greedy algorithm. Its O(N^3 log Z), where N is the number of denominations and Z is the greatest bill of the set.

You can find it in http://library.wolfram.com/infocenter/MathSource/5187/