Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:

$$ s = \sum_{i=1}^k n_i d_i\quad\text{with } n_i > 0, d_i > d_{i-1} $$

We start with the highest denomination $d$ not exceeding $s$ and subtract it. We repeat this process until $s$ is completely represented. As long as all denominations are available, this simple algorithm guarantees the minimum number of coins or bills used. (This is a little sketchy but I guess we are all familiar with it and it's not central to my question.)

My question is: what property of $d_i$ makes this work? I once heard that the value of any coin must be bigger than the sum of all coins of lower denomination for the greedy algorithm to work. This holds for the typical denomination:

$$ 1,2,5,10,20,50,100 $$

However, I wasn't able to come up with a counter example or even a proof. Surely this problem has been studied and I would be glad to know more about it. In fact, I'm not even sure about the right tags -- feel free to edit them. I assume the algorithm to find the sum with the minimum number of coins becomes tricky when we no longer can assume that all denominations are available.

share|improve this question

4 Answers 4

up vote 15 down vote accepted

The greedy solution is not optimal in general, even for the case when the value of any coin is bigger than the sum of all coins of lower denomination. For example, suppose we have coins of denominations 25, 9, 4, and 1. For 37 cents, the greedy solution uses five coins: one 25, one 9, and three 1s. However, the optimal solution is four coins: one 25 and three 4s.

The problem of finding the minimum number of coins given a set of denominations is called the change-making problem. It's a variant of the famous knapsack problem and is known to be difficult in the general case.

An integer-programming formulation for the change-making problem was given in the answer to this math.SE question: On problems of coins totaling to a given amount.

Added: While the Wikipedia article on the change-making problem claims that the greedy algorithm is optimal for U.S. coins, it provides no proof. The article "Canonical Coin Systems for Change-Making Problems" discusses characterizations for when the greedy algorithm is optimal for coin systems of up to five denominations. It also implies that for systems of larger than five denominations determining when the greedy algorithm is optimal is still an open problem.

share|improve this answer
1  
Thanks! So the property I heard about was too weak but I assume the denomination of, say, the US currency does still guarantee an optimal solution for the greedy algorithm when all coins are available. If so, some stronger property must hold. –  Christian Lindig Mar 6 '11 at 6:51

Here's an algorithm I think should decide if, for a given set of denominations, the greedy change making algorithm is optimal. coins(value, set of denominations) is a function that returns the minimal number of coins needed to make the value with those denominations.

Given set D of denominations

let m = largest element of D
for each value v from 2*m - 1 down to 1
   let d = largest element of D <= v
   if (coins(v-d,D) >= coins(v, D-d))
      return false
return true

This doesn't do much to tell you what properties will result in the greedy algorithm being optimal, but it shows that the property is easily computable.

Edit: A dynamic programming solution for function coins.

Without a loss of generality, let's impose an order on the way you can pick coins. Once you drop down to a lower denomination, you can't go back above that denomination. Given this, its obvious that you always have two choices, pick a coin of the denomination you are on, or drop down to a lower denomination. This means the optimal number of coins is coins(v, D) = min(coins(v-d,D)+1,coins(v,D-d)), where d is the the current, highest denomination. coins(v=0,D) = 0, coins(v<0,D) = infinity, and coins(v>0,D={}) = infinity.

We can calculate coins(v,D) by first calculating all possible subproblems. Construct a two dimensional array DP with |D| rows and 2*m columns. DP[i][j] represents the minimal number of coins it takes to make value j using only coins up to the ith denomination.

(note, pseudocode uses 0 indexed arrays)

array DP[D.size][2*m] initialized to -1
for(int i=0; i<D.size; i++)
    for(int j=0; j<2*m; j++)
        DP[i][j] = calc_coins(j,i)

function calc_coins(int v, int d)
    if(v<0 || d<0)
         return infinity
    if(v==0)
         return 0
    if(DP[d][v] >= 0)
         return DP[d][v]
    int pick = calc_coins(v-D[d], d) + 1
    int drop_down = calc_coins(v,d-1)
    return min(pick, drop_down)

Once this table is calculated, all calls to coins(v,D) that will be made in the outer algorithm will be constant time. A call to coins(v,D) is equivalent to a table lookup at DP[D.size - 1][v] because we are always shaving off the highest denominations in D in the outer algorithm.

share|improve this answer
    
Trying to understand your answer... I don't follow the "coins" function. It seems like it is able to figure out whether the greedy solution is optimal. But isn't that what the outer algorithm is trying to test for in the first place? –  Mike Spivey Mar 21 '11 at 16:38
    
@Mike Spivey: coins figures out the optimal way to make change given that particular value and those particular coin types, with no assumptions about greedyness. There's a well known dynamic programming algorithm to do this. The outer algorithm is testing to see if you can use a greedy algorithm to make change optimally using those coins for any value. –  Null Set Mar 21 '11 at 16:46
1  
@Null Set: O.K.; I understand now. The dynamic programming algorithm can be slow, though (the change-making problem is known to be NP-hard). Wouldn't it then be faster, for each $v$, to find the greedy solution (which would be fast), call "coins" once, and compare - rather than calling "coins" twice for each $v$? –  Mike Spivey Mar 21 '11 at 16:55
    
@Mike Spivey: Due to how the DP algorithm defines its subproblem, if you have calculated coins(v,D), you have also already calculated and stored coins(v-d,D) and coins(v,D-d), which makes later calls be constant time. I think I better just add the algorithm to the answer to make sure neither of us is making some wrong assumptions. –  Null Set Mar 21 '11 at 17:33
    
@Mike Spivey: See my edit. Am I crazy or is that a polynomial time solution? Is there some case I'm not thinking of that this doesn't cover that makes this NP-hard? –  Null Set Mar 21 '11 at 19:07

The paper D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005 offers an $O(n^3)$ algorithm for deciding whether a coin system has the property you want, where $n$ is the number of different kinds of coins. From the abstract:

We then derive a set of $O(n^2)$ possible values which must contain the smallest counterexample. Each can be tested with $O(n)$ arithmetic operations, giving us an $O(n^3)$ algorithm.

The paper is quite short.

share|improve this answer

I recently came up with 1 solution that seemed to show if the given 2 conditions are satisfied, the greedy algorithm would yield the optimal solution.

a) The G.C.D (All the denominations except 1) = 2nd Smallest denomination.

b) The sum of any 2 consecutive denominations must be lesser than the 3rd consecutive denomination.

For eg. c2 + c3 < c4.

(Where c1 = 1; c2, c3, c4 are coin denominations in ascending order).

I understand this is not a complete solution. However, I believe that if these 2 conditions are met, the greedy algorithm will yield the optimal solution.

share|improve this answer
    
This would be more useful if accompanied by a proof. Duplicate answer. –  robjohn Mar 6 '13 at 9:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.