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$
3
  • $\begingroup$ Is $k$ the number of distinct "denominations" of coins? $\endgroup$
    – hardmath
    Commented Oct 27, 2015 at 3:25
  • $\begingroup$ Yes. $k$ is the number of coins in the coin system. $\endgroup$
    – metro
    Commented Oct 27, 2015 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
    Commented Oct 27, 2015 at 16:17

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .