Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am thinking of the greedy algorithm for making change: basically take the largest denomination until you get within one largest denomination, take next denomination etc.

This algorithm works for most currencies to simplify making change. Of course, not all currencies conceivable yield optimal solutions with the greedy algorithm: for example if we have coins of denomination 25, 9, 4, 1, then the optimal solution for 37 dollars is 25,4,4,4 rather than the greedy 25,9,1,1,1.

However, in this case the greedy algorithm still works in the sense that it does find a viable solution. If we remove the 1-dollar coin, then 37 dollars would go 25,9, and then get stuck.

But in this case, we can't represent 2 dollars, and many other integers. So my conjecture is:

If there is a case where the greedy algorithm for making change fails to produce a solution, then there are non-trivial cases where no solution exists.

Non-trivial being, say, removing 1 dollar coins causes $1 to be impossible to represent, but this is considered trivial. I cannot find a counterexample. Is this true? Can we design a currency that would cause the greedy algorithm to completely fail to find a solution without backtracking, yet can represent (almost) all integer amounts of money?

share|improve this question
1  
I don't understand. –  Jorge Fernández Feb 12 at 3:38
4  
The simplest case is just $\{2,3\}$. The greedy algorithm fails for all amounts of the form $3k+1$, but only $1$ is not representable as a sum of $2$'s and $3$'s. –  mjqxxxx Feb 12 at 3:48

1 Answer 1

up vote 3 down vote accepted

How about $25,8,3,2$ and trying to make $34$? The greedy algorithm gets stuck after $25+8$, but all amounts except $1$ are solvable.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.