6

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?

tijko
  • 7,599
  • 11
  • 44
  • 64
  • the greedy algorithm just always picks the largest denomination coin that doesnt exceed the ammount still due – Joran Beasley Jul 27 '12 at 21:09
  • 1
    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 Jul 27 '12 at 21:19
  • @Blckknght I didn't think there was a way to use the **dict[key] = value** without overwriting the existing values. – tijko Jul 27 '12 at 21:30
  • 1
    `dict[key]=value` will overwrite any existing value at the `key`, but won't delete any other values from the dict. – Matt Jul 27 '12 at 21:41
  • @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 Jul 27 '12 at 21:44
  • @tijko: Yeah, `dict[key]=value` overwrites whatever value was previously stored under that key, but so does `dict.update({key:value})`. If you want to add your new value to a list, try using a `defaultdict` (from the `collections` module), with `list` as its `default_factory`, then using `dict[key].append(value)`. – Blckknght Jul 27 '12 at 22:17
  • @Blckknght **dict.update({key:value})** overwriting was the reason I used the `ways` dict. I've better check out defaultdict too. Thanks :) – tijko Jul 27 '12 at 22:24

3 Answers3

4

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)

Joran Beasley
  • 110,522
  • 12
  • 160
  • 179
  • I'm not sure if all of that was correct but, the recursive part is where I'm heading next so that bit was very helpful. I wanted to make sure that what I was doing with greedy-algorithm was right first because I had worked it in as an simpler exercise branched from that problem. – tijko Jul 27 '12 at 21:35
  • 1
    this maybe helpful also http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum – Joran Beasley Jul 27 '12 at 23:26
2

You've edited your question to ask what is the optimal way to make change for a given amount using a given set of coins; at least, I think that's the question you're asking. I'll assume that there is an unlimited number of each denomination of coin available, or at least enough that you can use as many coins of each denomination as you like.

Let's take for example the problem of making change for a dollar using coins of 1, 5, 10 and 25 cents; a dollar is 100 cents. The greedy algorithm always takes the biggest possible coin. Thus, at the first step, the biggest coin is less than or equal to the target amount, so add a 25 cent coin to the output and reduce the target to 75 cents. At the second step, the biggest coin is less than or equal to the reduced target, so add a 25 cent coin to the output and reduce the target to 50 cents. At the third step, the biggest coin is less than or equal to the reduced target, so add a 25 cent coin to the output and reduce the target to 25 cents. At the fourth step, the biggest coin is less than or equal to the reduced target, so add a 25 cent coin and reduce the target to 0 cents. Now there is nothing left to do, so the output is four 25 cent coins.

Since that wasn't very interesting, let's try again with a target of 47 cents. The first step outputs a 25 cent coin and reduces the target to 22 cents. Now it is no longer possible to output a 25 cent coin, so output the biggest coin less than or equal to the reduced target, which is a 10 cent coin, and reduce the target to 12 cents. At the third step, the biggest coin less than or equal to the reduced target is 10 cents, so output that coin and reduce the target to 2 cents. The next two steps will each output a 1 cent coin and reduce the target to zero. So the output is one 25 cent coin, two 10 cent coins, and two 1 cent coins, for a total of 47 cents.

I'll leave it to you to write the code from there. And as you said, that has nothing to do with Euler 76.

UPDATE responding to the first comment, which has now disappeared.

I'm not sure what to call your code. I guess greedy is a good enough word. Here's how I would have done it, with debugging output included so you can see the intermediate steps:

def greedy(amount, denoms):
    result = []
    while (amount > 0):
        print amount, denoms, result
        if (amount >= denoms[0]):
            num = amount // denoms[0]
            amount -= (num * denoms[0])
            result.append([denoms[0], num])
        denoms = denoms[1:]
    return result

print greedy(100, [25,10,5,1])
print ""
print greedy(100, [10,5,1])
print ""
print greedy(100, [5,1])
print ""
print greedy(100, [1])
print ""
print greedy(47, [25,10,5,1])

And the output is:

100 [25, 10, 5, 1] []
[[25, 4]]

100 [10, 5, 1] []
[[10, 10]]

100 [5, 1] []
[[5, 20]]

100 [1] []
[[1, 100]]

47 [25, 10, 5, 1] []
22 [10, 5, 1] [[25, 1]]
2 [5, 1] [[25, 1], [10, 2]]
2 [1] [[25, 1], [10, 2]]
[[25, 1], [10, 2], [1, 2]]

Does that help?

user448810
  • 17,381
  • 4
  • 34
  • 59
1

Euler 76 asks you to calculate the partitions of a number. It is not the coin problem and it is not a greedy algorithm. The method for counting the partitions of a number is due to Euler (surprise!) and you can look it up in most algorithms or math texts, or on Google. Your program should execute nearly instantly.

By the way, the answer at Project Euler is 1 less than the normal calculation of P(100) because it ignores the convention that P(0)=1. Thus, after you write a function to calculate partitions, the answer to Euler 76 is P(100)-1.

I've discussed partitions twice on my blog, once when I calculated the number of partitions and again when I enumerated all the partitions.

user448810
  • 17,381
  • 4
  • 34
  • 59
  • I was aware that this wasn't the way to solve that particular question. I wanted to make sure my thoughts and code were correct about the coin problem and greedy algorithm. I edited my post to explicitly say this. I am going to next work out a more optimized approach to solving Euler 76 too so the rest of what you mentioned should be of help. – tijko Jul 27 '12 at 23:48
  • I'll give a separate answer instead of responding in a comment. – user448810 Jul 27 '12 at 23:51