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

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?

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.

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

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.

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.

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.

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.")

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

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