Greedy algorithm and coin algorithm?

Viewed 9148

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?

3 Answers
Related