1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I don't understand. $\endgroup$ – Jorge Fernández Hidalgo Feb 12 '14 at 3:38
  • 4
    $\begingroup$ 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. $\endgroup$ – mjqxxxx Feb 12 '14 at 3:48
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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