Why does the greedy coin change algorithm not work

问题:

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?

回答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.

回答2:

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.

回答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.

回答4:

An easy to remember case is that any set of coins such that, if they are sorted in ascending order and you have:

coin[0] = 1
coin[i+1] >= 2 * coin[i], for all i = 0 .. N-1 in coin[N]

Then a greedy algorithm using such coins will work.

Depending on the range you're querying, there may be more optimal (in terms of number of coins required) allocation. An example of this is if you're considering the range (6..8) and you have the coins <6, 7, 8> instead of <1, 2, 4, 8>.

The most efficient allocation of coins that is complete over N+ is at equality of the above set of rules, giving you the coins 1, 2, 4, 8 ...; which merely is the binary representation of any number. In some sense, conversation between bases is a greedy algorithm in itself.

A proof on the >= 2N inequality is provided by Max Rabkin in this discussion: http://olympiad.cs.uct.ac.za/old/camp0_2008/day1_camp0_2008_discussions.pdf