3
$\begingroup$

Related to the paper: http://arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf and coin-change problem in general.

We say that a coin system of coins canonical if the greedy algorithm to the coin change-making problem (https://en.wikipedia.org/wiki/Change-making_problem) indeed produces the optimal solution.

Now instead I want to make a canonical coin system consisting of some positive integer $k$ coins (so I want to know for any $k$) such that a greedy solution is the only possible optimal solution.

How can this be done? Would the spacing between two coin denomations explode?

$\endgroup$
  • $\begingroup$ Is $k$ the number of distinct "denominations" of coins? $\endgroup$ – hardmath Oct 27 '15 at 3:25
  • $\begingroup$ Yes. $k$ is the number of coins in the coin system. $\endgroup$ – metro Oct 27 '15 at 3:42
  • $\begingroup$ I'm not sure how canonical we can say it is, but any mixed radix system of denominations will provide unique solutions with minimum coin count and this achieved by "greedy" allocation of biggest coins first. $\endgroup$ – hardmath Oct 27 '15 at 16:17

Your Answer

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

Browse other questions tagged or ask your own question.