Why does the greedy coin change algorithm not work for some coin sets?
Solution 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:
- S is a finite nonempty set
- 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
- 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.
Solution 2:
In any case where there is no coin whose value, when added to the lowest denomination, is lower than twice that of the denomination immediately less than it, the greedy algorithm works.
i.e. {1,2,3} works because [1,3] and [2,2] add to the same value however {1, 15, 25} doesn't work because (for the change 30) 15+15>25+1
Solution 3:
A coin system is canonical if the number of coins given in change by the greedy algorithm is optimal for all amounts.
This paper offers an O(n^3) algorithm for deciding whether a coin system is canonical, where n is the number of different kinds of coins.
For a non-canonical coin system, there is an amount c for which the greedy algorithm produces a suboptimal number of coins; c is called a counterexample. A coin system is tight if its smallest counterexample is larger than the largest single coin.
Solution 4:
This is a recurrence problem. Given a set of coins {Cn, Cn-1, . . ., 1}, such that for 1 <= k <= n, Ck > Ck-1, the Greedy Algorithm will yield the minimum number of coins if Ck > Ck-1 + Ck-2 and for the value V=(Ck + Ck-1) - 1, applying the Greedy Algorithm to the subset of coins {Ck, Ck-1, . . ., 1}, where Ck <= V, results in fewer coins than the number resulting from applying the Greedy Algorithm to the subset of coins {Ck-1, Ck-2, . . ., 1}.
The test is simple: for `1 <= k <= n test the number of coins the Greedy Algorithm yields for a value of Ck + Ck-1 - 1. Do this for coin set {Ck, Ck-1, . . ., 1} and {Ck-1, Ck-2, . . ., 1}. If for any k, the latter yields fewer coins than the former, the Greedy Algorithm will not work for this coin set.
For example, with n=4, consider the coin set {C4, C3, C2, 1} = {50,25,10,1}. Start with k=n=4, then V = Cn + Cn-1 - 1 = 50+25-1 = 74 as test value. For V=74, G{50,25,10,1} = 7 coins. G{25, 10, 1} = 8 coins. So far, so good. Now let k=3. then V=25+10-1=34. G{25, 10, 1} = 10 coins but G{10, 1} = 7 coins. So, we know that that the Greedy Algorithm will not minimize the number of coins for the coin set {50,25,10,1}. On the other hand, if we add a nickle to this coin set, G{25, 10, 5, 1} = 6 and G{10, 5, 1} = 7. Likewise, for V=10+5-1=14, we get G{10, 5, 1} = 5, but G{5,1} = 6. So, we know, Greedy works for {50,25,10,5,1}.
That begs the question: what should be the denomination of coins, satisfying the Greedy Algorithm, which results in the smallest worst case number of coins for any value from 1 to 100? The answer is quite simple: 100 coins, each with a different value 1 to 100. Arguably this is not very useful since it linear search of coins with every transaction. Not to mention the expense of minting so many different denominations and tracking them.
Now, if we want to primarily minimize the number of denominations while secondarily minimizing the resulting number of coins for any value from 1 to 100 produced by Greedy, then coins in denominations of powers of 2: {64, 32, 16, 8, 4, 2, 1} result in a maximum of 6 coins for any value 1:100 (the maximum number of 1's in a seven bit number whose value is less than decimal 100). But this requires 7 denominations of coin. The worst case for the five denominations {50, 25, 10, 5, 1} is 8, which occurs at V=94 and V=99. Coins in powers of 3 {1, 3, 9, 27, 81} also require only only 5 denominations to be serviceable by Greedy but also yield a worst case of 8 coins at values of 62 and 80. Finally, using any the five denomination subset of {64, 32, 16, 8, 4, 2, 1} which cannot exclude '1', and which satisfy Greedy, will also result in a maximum of 8 coins. So there is a linear trade-off. Increasing the number of denominations from 5 to 7 reduces the maximum number of coins that it takes to represent any value between 1 and 100 from 8 to 6, respectively.
On the other hand, if you want to minimize the number of coins exchanged between a buyer and a seller, assuming each has at least one coin of each denomination in their pocket, then this problem is equivalent to the fewest weights it takes to balance any weight from 1 to N pounds. It turns out that the fewest number of coins exchanged in a purchase is achieved if the coin denominations are given in powers of 3: {1, 3, 9, 27, . . .}.
See https://puzzling.stackexchange.com/questions/186/whats-the-fewest-weights-you-need-to-balance-any-weight-from-1-to-40-pounds.