A well-known Change-making problem, which asks
how can a given amount of money be made with the least number of coins of given denominations
for some sets of coins (50c, 25c, 10c, 5c, 1c) will yield an optimal solution by using a greedy algorithm (grab the highest value coin). For some other sets one have to use a dynamic programming.
Is there any way to prove whether for a given set of coins a greedy solution will always yield an optimal solution? Coin denomination can be any natural number (not only smaller then 100) and there can be any number of different coin denominations.