Greedy Or Not?

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] :

1
2
3
4
5
6
7
8
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] :

1
2
3
4
5
6
7
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.

×

Problem Loading...

Note Loading...

Set Loading...