Greedy algorithm and coin algorithm?

Question

I've been working on some problems/exercises on Project Euler hoping to practice/learn some optimal algorithms and programming idioms with python.

I came across a problem which asked to find all the unique combinations using at least two values to sum to 100. In researching this problem I came across people referring to the coin problem and the greedy algorithm which is what this question is about.

I had heard of the greedy algorithm before but, never understood or used it. I thought I would give it a try. I still am unsure of whether this is the proper way of doing it.

def greedy(amount):
    combos = {}
    ways = {}
    denominations = [1,5,10,25]
    ## work backwards? ##
    denominations.reverse()
    for i in denominations:
    ## check to see current denominations maximum use ##
        v = amount / i
        k = amount % i
    ## grab the remainder in a variable and use this in a while loop ##
        ways.update({i:v})
    ## update dictionarys ##
        combos.update({i:ways})
        while k != 0:
            for j in denominations:
                if j <= k:
                    n = k/j
                    k = k % j
                    ways.update({j:n})
                    combos.update({i:ways})
        ways = {}
    return combos

I know this isn't the way to go about solving the Euler question but, I wanted to understand and learn an optimal way to use this algorithm. My question is, would this be considered a proper greedy-algorithm? If not what am I doing wrong. If correct could I improve optimize?

the greedy algorithm just always picks the largest denomination coin that doesnt exceed the ammount still due — Joran Beasley
This is peripheral to your main question, but the code dict.update({key:value}) seemed very strange to me (and so I wondered if something subtle was going on). But no, it's identical in effect to the much clearer dict[key]=value, which I'd suggest using instead. The dict.update() method is mostly useful when you have many values to add, or another dictionary (e.g. dict.update(dict2)). — Blckknght
@Blckknght I didn't think there was a way to use the dict[key] = value without overwriting the existing values. — tijko
dict[key]=value will overwrite any existing value at the key, but won't delete any other values from the dict. — Matt
@Blckknght, its a matter of how I want it to look now in the data structure. I was going for a {25:1,1,3} but I'd have to put those values in another dict or list correct? I think the dict would be best or have the denominations in a list individually returned like in Jorans function below. — tijko

Joran Beasley Joran Beasley · Accepted Answer · 2012-07-27T21:18:52

The greedy coin algorithm computes the optimal way to make change for a given amount due. It works with our denominations of coins but could fail with made up denominations of coins (eg. a 7 cent coin and a 12 cent coin)

here is a recursive implementation of it

>>> def pickBest(coins,due):
...     if due == 0: return []
...     for c in coins:
...        if c<= due: return [c] + pickBest(coins,due-c)
...
>>> coins = [1,5,10,25]
>>> coins = sorted(coins,reverse=True)
>>> coins
[25, 10, 5, 1]
>>> print pickBest(coins,88)
[25, 25, 25, 10, 1, 1, 1]

however I dont think this will help you much with the problem as you stated it

you would likely want to think of it as a recursive problem

100 = 99 + 1
100 = 98 + 2  (2 = 1 + 1)
100 = 98 + (1 + 1)
100 = 97 + 3 (3 = 1 + 2)
100 = 97 + 2+1 (recall 2 = 1+1)
100 = 97 + 1+1 + 1
...

at least thats what I think, I might be wrong..(in fact i think I am wrong)

Greedy algorithm and coin algorithm?

3 Answers