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?

Turaco

The answer depends a lot on what the algorithm does: it's easy to get greedy with coins, you should tell us what the algorithm does, and how it does it. – Gid

... what is the actual problem that the algorithm is supposed to solve? – Sites

Ok, I guess i didn't ask the question right. What about a set of denominations must be true for the algorithm to not work. Ex. make 30 cents from (25, 15, 1) greedy gives us 25,1,1,1,1,1 but 15 15 is better. What about 25 15 and 1 make the greedy not work? – Turaco

Look at whether they form a en.wikipedia.org/wiki/Matroid. – Numbersnumbfish

This is a good question, not sure why it was downvoted. S/he wants an explanation of the constraints that a set of coins must satisfy in order for the greedy algorithm (which always selects the largest coin that will fit) to select a minimum number of coins to pay any specified amount. – Anaptyxis

@Anaptyxis That can be inferred from the OP's comment, but not from the question. The question itself contains no hint of what the algorithm is supposed to do, and thus it is not a good question. – Ruffo

@DanielFischer: Fair enough. Good on you for fixing the question. – Anaptyxis

I was looking for the similar question .. Why does the greedy coin change algorithm work for some coin sets? So there is a paper which gives a very ugly expression about the sufficient condition for greedy solution to be the optimal one. trust me you dont want to read that :-) – Mccandless

I'm voting to close this question as off-topic because it belongs on math.stackexchange.com. – Chihuahua

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.

Rutland

This argument is not correct. If S = {25,10,5,1}, V = 30, A={25}, B={10,10,10}, the same argument shows that {S,I} is not a matroid, since {25, 10) is not in I. On the other hand, the greedy algorithm works for this choice of S (as one shows in CLRS, Problem 16-1a). Presence of a certain matroid structure is a sufficient but not necessary condition for correctness of the greedy algorithm. – Athanasius

@TobiasHagge Do we have a condition that tells us greedy algorithm will fail for a set? – Sigfrid

@dh16, Pearson, "A Polynomial-time Algorithm for the Change-Making Problem", Operation Research Letters 33:3, pp 231-234 (may 2005) gives an algoritm to check. No simple condition, unfortunately. – Disarrange

Answer 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

Figueroa

Nice answer. This is what i was looking for :) – Wallache

Passing your test guarantees greedy approach works but the inverse is not true. Greedy works for {1, 5, 15, 25}. – Antevert

This answer seems wrong. Greedy algorithm doesn't give an optimal solution for coins {1, 8, 20} and target value of 24, even though 8 + 8 = 16 < 21 = 20 + 1. – Blackmail

I don't follow, this answer is just outright wrong? Why does this have so many upvotes? Am I missing something? – Ulna

Answer 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. Importantly, a non-canonical coin system will have a c that is smaller than the sum of values of the two largest coins, so it can be found in finite time.

As an aside, a coin system is called "tight" if its smallest counterexample is larger than the largest single coin.

Kaiserslautern

It also references other tests, including the fact that the smallest counter-example must be lower than the sum of the two largest coins. – Antoniaantonie

This answer appears to be right, but trivially so. "A coin system is canonical if it passes the test for being canonical" (obligatory XKCD xkcd.com/703). – Nikko

Answer 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.

Changeable

Answer 5

Theory:

If the greedy algorithm always produces an optimal answer for a given set of coins, you say that set is canonical.

Stating the best known algorithmic test [O(n^3)] for determining whether an arbitrary set of n coins is canonical, as succinctly as I can:

[c1,c2,..cn] is canonical iff for all w_ij |G(w_ij)| = |M(w_ij)|, 1 < i <= j <= n 

where [c1,c2,...cn] is the list of coin denominations sorted descending with cn = 1

G(x) represents the coin vector result of running the greedy algorithm on input x, (returned as [a1, a2,..., an] where ai is the count of ci)

M(x) represents a coin vector representation of x which uses the fewest coins

|V| represents the size of the coin vector V: the total number of coins in the vector

and w_ij is the evaluated value of the coin vector produced by G(c_(i-1) - 1) after incrementing its j'th coin by 1 and zeroing all its coin counts from j+1 to n.

Implementation (JavaScript):

/**
 * Check if coins can be used greedily to optimally solve change-making problem
 * coins: [c1, c2, c3...] : sorted descending with cn = 1
 * return: [optimal?, minimalCounterExample | null, greedySubOptimal | null] */
function greedyIsOptimal(coins) {
  for (let i = 1; i < coins.length; i++) {
    greedyVector = makeChangeGreedy(coins, coins[i - 1] - 1)
    for (let j = i; j < coins.length; j++) {
      let [minimalCoins, w_ij] = getMinimalCoins(coins, j, greedyVector)
      let greedyCoins = makeChangeGreedy(coins, w_ij)
      if (coinCount(minimalCoins) < coinCount(greedyCoins))
        return [false, minimalCoins, greedyCoins]
    }
  }
  return [true, null, null]
}

// coins [c1, c2, c3...] sorted descending with cn = 1 => greedy coinVector for amount
function makeChangeGreedy(coins, amount) {
  return coins.map(c => {
    let numCoins = Math.floor(amount / c);
    amount %= c
    return numCoins;
  })
}
// generate a potential counter-example in terms of its coinVector and total amount of change
function getMinimalCoins(coins, j, greedyVector) {
  minimalCoins = greedyVector.slice();
  minimalCoins[j - 1] += 1
  for (let k = j; k < coins.length; k++) minimalCoins[k] = 0
  return [minimalCoins, evaluateCoinVector(coins, minimalCoins)]
}
// return the total amount of change for coinVector
const evaluateCoinVector = (coins, coinVector) =>
  coins.reduce((change, c, i) => change + c * coinVector[i], 0)

// return number of coins in coinVector
const coinCount = (coinVector) =>
  coinVector.reduce((count, a) => count + a, 0)

/* Testing */
let someFailed = false;
function test(coins, expect) {
  console.log(`testing ${coins}`)
  let [optimal, minimal, greedy] = greedyIsOptimal(coins)
  if (optimal != expect) (someFailed = true) && console.error(`expected optimal=${expect}
  optimal: ${optimal}, amt:${evaluateCoinVector(coins, minimal)}, min: ${minimal}, greedy: ${greedy}`)
}
// canonical examples
test([25, 10, 5, 1], true) // USA
test([240, 60, 24, 12, 6, 3, 1], true) // Pound Sterling - 30
test([240, 60, 30, 12, 6, 3, 1], true) // Pound Sterling - 24
test([16, 8, 4, 2, 1], true) // Powers of 2
test([5, 3, 1], true) // Simple case

// non-canonical examples
test([240, 60, 30, 24, 12, 6, 3, 1], false) // Pound Sterling
test([25, 12, 10, 5, 1], false) // USA + 12c
test([25, 10, 1], false) // USA - nickel
test([4, 3, 1], false) // Simple cases
test([6, 5, 1], false)

console.log(someFailed ? "test(s) failed" : "All tests passed.")

Nunez

Answer 6

Well we really need to reformulate this question...greedy algorithm essentially doing is that it tries to obtain the target value using the provided coin denominations. Any change you make to the greedy algorithm simply change the way of reaching the target value. It does not account for the minimum coins used.... To put in a better way a safe move does not existed for this problem. A higher denomination coin may yield target value quickly but it is not a safe move. Example {50,47,51,2,9} to obtain 100 Greedy choice would be to take highest denomination coin to reach 100 more quickly.. 51+47+2 Well it reached but 50+50 should do..

Lets take {50,47,51,9} to obtain 100 If it makes a greedy choice of highest coin 51 it needs for 49 from the set. It does not know whether it is possible or not. It tries to reach 100 but it cannot And changing greedy choice simply changes the way of reaching the 100 These types of problems creates set of solutions and forms of branch of decision tree.

Argil

Answer 7

Today,I solved question similar to this on Codeforces(link will be provided at then end). My conclusion was that for coin-change problem to get solved by Greedy alogrithm, it should statisfy following condition:-

1.On sorting coin values in ascending order, all values to the greater than current element should be divisible by the current element.

e.g. coins = {1, 5, 10, 20, 100}, this will give correct answer since {5,10, 20, 100} all are divisible by 1,{10,20, 100} all are divisible by 5,{20,100} all are divisible by 10,{100} all are divisible by 20.

Hope this gives some idea.

996 A - Hit the lottery https://codeforces.com/blog/entry/60217

Rayshell

What about 1 2 5 10 20 50 100 ? – Starry