Why does the greedy coin change algorithm not work for some coin sets?

Question

I understand how the greedy algorithm for the coin change problem (pay a specific amount with the minimal possible number of coins) works - it always selects the coin with the largest denomination not exceeding the remaining sum - and that it always finds the correct solution for specific coin sets.

But for some coin sets, there are sums for which the greedy algorithm fails. For example, for the set {1, 15, 25} and the sum 30, the greedy algorithm first chooses 25, leaving a remainder of 5, and then five 1s for a total of six coins. But the solution with the minimal number of coins is to choose 15 twice.

What conditions must a set of coins fulfil so that the greedy algorithm finds the minimal solution for all sums?

Answer 1

A set which forms a matroid (https://en.wikipedia.org/wiki/Matroid) can be used to solve the coin changing problem by using greedy approach. In brief, a matroid is an ordered pair M = (S,l) satisfying the following conditions:

1. S is a finite nonempty set
2. l is a nonempty family of subsets of S, called the independent subsets,such that if B->l and A is a subset of B, then A -> l
3. If A-> l, B-> l and |A| < |B|, then there is some element x-> B-A such that A U {x} ->l

In our question of coin changing, S is a set of all the coins in decreasing order value We need to achieve a value of V by minimum number of coins in S

In our case, l is an independent set containing all the subsets such that the following holds for each subset: the summation of the values in them is <=V

If our set is a matroid, then our answer is the maximal set A in l, in which no x can be further added

To check, we see if the properties of matroid hold in the set S = {25,15,1} where V = 30 Now, there are two subsets in l: A = {25} and B= {15,15} Since |A| < |B|, then there is some element x-> B-A such that A U {x} ->l (According 3) So, {25,15} should belong to l, but its a contradiction since 25+15>30

So, S is not a matroid and hence greedy approach won't work on it.