Q:

Most optimal coin fit for a given sum of money

How would you reach a given sum in the most optimal manner possible given a set of coins ?
Let's say that in this case we have random numbers of 1, 5, 10, 20 and 50 cent coins with the biggest coins getting the priority.
My first intuition would be to use all the biggest coins possible to fit and then use up the next smallest coin in value if the sum is exceeded.
Would this do or are there any shortfalls to this approach ? Are there any more efficient approaches ?

A:

There are shortfalls to simply giving out the largest coins first.
Let's say your vending machine is out of every coin except twenty each of 50c, 20c and 1c coins and you have to deliver 60c in change.
A "prioritise-largest" (or greedy) scheme will give you eleven coins, one 50c coin and ten 1c coins.
The better solution is three 20c coins.
Greedy schemes only give you local optimum solutions. For global optima, you generally need to examine all possibilities (though there may be minimax-type algorithms to reduce the search space) to be certain which, for delivering change, is usually quite within the limits of computability.

A:

Greedy Algorithms (what you are doing right now) are usually chosen for this type of things and implemented as Final State Machines to be used in vending machines (for this particular case).

The greedy algorithm determines the minimum number of coins to give
  while making change. These are the steps a human would take to emulate
  a greedy algorithm

