Greedy Or Not?

Computer Science Level 3

There is a list of coins : $L = \{100000,10000,1000,100,10,1\}$

You want to know the minimum number of coins needed to achieve value $V$ , so you asked the two best programmers in the world, Alice and Bob, and each of them proposed a different algorithm:

Alice [Dynamic Programming] :

def dpMakeChange(L, V, minCoins):
    for cents in range(V+1):        
        coinCount = cents
        for j in [c for c in L if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
                coinCount = minCoins[cents-j] + 1
        minCoins[cents] = coinCount
    return minCoins[V]

Bob [Greedy] :

def greedyMakeChange(L, V):
    minCoin = 0
    for change in L:
        while V >= change:
            V -= change
            minCoin += 1
    return minCoin

Which is the better algorithm? Of course, correctness is your top priority, then the speed.

Alice Bob Both performs equally well

1 solution

Agnishom Chattopadhyay
Jul 1, 2016

Here is Bob's Greedy Algorithm summarized: Use the largest currency available as many times as you can. For example, if he has $3456: he splits it up into 3 $1000's, 4 $100's, 5 $10's and 6 $1's.

To prove that this indeed yields the minimum number of coins, assume on the contrary it does not. This means that there is a value V for which the optimal way to get it in terms of these coins does not use the largest available coin as many times as it could, at some point.

Let's say that the largest such coin in this splitting which is not greedily used is of the value $10^n$ . Let us further assume that this solution uses $x$ of those $10^n$ coins less than the greedy solution. Now, it is easy to see that to make up for that extra $x \cdot 10^n$ amount, we have to use either $10x$ coins of value $10^{n-1}$ , or $100x$ coins of value $10^{n-2}$ , or ...

But this cannot be the case since we said that this solution is optimal. Contradiction!

Hence, the greedy solution is indeed optimal.

Now that we've proved the correctness of the greedy algorithm, we need to show that it is indeed faster.

The dynamic programming algorithm computes the answer for all values from 1 to V even irrespective of the coin sizes. However, the greedy algorithm does operations only at points which are multiples of the coin sizes.

How would you determine if greedy solution can be applied to the set of coins?

Christopher Boo - 4 years, 11 months ago

In the event that the coins are in Geometric Progression, it is always fine to use the greedy algorithm

Agnishom Chattopadhyay - 4 years, 11 months ago

How about non-GP? For example, Zeckendorf's Theorem states that if all the coins are Fibonacci number smaller than $V$ then Greedy works. Given an arbitrary coin system, what is the algorithm to show that it can be Greedy?

Christopher Boo - 4 years, 11 months ago

@Christopher Boo – That is a hard question. What do you think is the answer?

Agnishom Chattopadhyay - 4 years, 11 months ago

@Agnishom Chattopadhyay – I don't know too. I saw the answer in CS Stackexchange but haven't fully understand the author's explanation.

Christopher Boo - 4 years, 11 months ago

@Christopher Boo – Jee! That's more complicated than I thought

Agnishom Chattopadhyay - 4 years, 11 months ago

Greedy Or Not?

1 solution

0 pending reports