Greedy algorithm and coin acceptor?

Question

I worked on some problems / exercises in Project Euler, hoping to practice / learn some optimal programming algorithms and idioms with python.

I ran into a problem that asked me to find all the unique combinations, using at least two values ​​to sum up to 100. When researching this problem, I came across people referring to the coin problem and the greedy algorithm in question on this issue.

I had heard of a greedy algorithm before, but I never understood or used it. I thought I would try. I'm still not sure how right this is.

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 that this is not a way to solve Euler's question, but I wanted to understand and study the best way to use this algorithm. My question is, would this be considered the right greedy algorithm? If not what I'm doing wrong. If correct, can I improve the optimization?

Answer 1

The greedy coin algorithm calculates the best way to make changes for a given amount. It works with our coin denominations, but may fail with crafted coin denominations (for example, a 7-cent coin and a 12-cent coin).

here is a recursive implementation

 >>> 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 do not think that this will help you deal with the problem as you stated it.

you probably 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 this is what I think I can be wrong .. (actually I think I'm wrong)

Answer 2

You edited your question to ask what is the best way to make changes for a given amount using a given set of coins; at least I think the question you are asking. I assume that there is an unlimited amount of each coin value, or at least enough so that you can use as many coins of each denomination as you want.

Take, for example, the problem of making changes to the dollar using coins of 1, 5, 10, and 25 cents; The dollar is 100 cents. The greedy algorithm always takes the largest coin possible. Thus, at the first stage, the largest coin is less than or equal to the specified amount, so add a coin by 25 cents to the output and reduce the target to 75 cents. In the second step, the largest coin is less than or equal to the reduced target, so add a 25 cents coin to the output and reduce the target to 50 cents. In the third step, the largest coin is less than or equal to the reduced target, so add a 25 cents coin to the exit and reduce the target to 25 cents. In the fourth step, the largest coin is less than or equal to the reduced target, so add a 25 cents coin and reduce the target to 0 cents. Now there is nothing to do, so the output is four coins in denominations of 25 cents.

Since it was not very interesting, try again with a goal of 47 cents. At the first stage, a coin with a value of 25 cents is displayed and reduced to 22 cents. Now it is no longer possible to issue a coin of 25 cents, so withdraw the largest coin, less than or equal to the reduced target, which is a coin of 10 cents, and reduce the target to 12 cents. In the third stage, the largest coin is less than or equal to the reduced target - 10 cents, so withdraw this coin and reduce the target to 2 cents. The next two steps will set the coin at 1 cent and reduce the target to zero. Thus, the output is one coin of 25 cents, two coins of 10 cents and two coins of 1 cents, for a total of 47 cents.

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

UPDATE responds to the first comment that has now disappeared.

I'm not sure what to name your code. Perhaps greedy is a good enough word. Here is how I would do it, with debug output turned on 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 result:

 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 it help?

Answer 3

Euler 76 asks you to calculate the splits of a number. This is not a coin problem, and it is not a greedy algorithm. The method of counting sections of a number is related to Euler (surprise!), And you can find it in most algorithms or mathematical texts or on Google. Your program should run almost instantly.

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

I discussed sections twice on my blog, once when I calculated the number of sections and again when I listed all sections.