1
$\begingroup$

There is a greedy algorithm for coin change problem : using most valuable coin as possible. How We can find a quick method to see which of following sets of coin values this algoithms cannot find optimal solutions (i.e the minimum number of coins). We assume that we have infinitely many coins of each type.

Examples: $\{1, 4, 7\}$, $\{1, 2, 5\}$, $\{1, 7, 10\}$, $\{1, 5, 10\}$

Why just the third set is not optimal and other sets is optimal?

I see one paper on Link but not familiar with me.

$\endgroup$
10
  • $\begingroup$ cannot find optimal solutions for what? $\endgroup$
    – fleablood
    Feb 12, 2016 at 22:15
  • $\begingroup$ @fleablood I correct it, this algorithm cannot find optimal solution for third set. why ? $\endgroup$ Feb 12, 2016 at 22:16
  • $\begingroup$ Are you asking for the definition of "optimal"? Or for general theorems? In this case, the greedy algorithm is sub-optimal for the third group (eg. $14=7+7$ is better than $14=10+1+1+1+1$. Is that what you were after? $\endgroup$
    – lulu
    Feb 12, 2016 at 22:22
  • $\begingroup$ @lulu exactly my problem is here. how you quickly find that this is not optimal? if I didn't mentioned the third set is not optimal, you find it? create a counterexample is not very easy? $\endgroup$ Feb 12, 2016 at 22:27
  • $\begingroup$ It looks like Theorem 4 in the linked-to paper contains the answer. $\endgroup$ Feb 12, 2016 at 22:30

1 Answer 1

1
$\begingroup$

Theorem 4 in the OP's linked-to paper says that a set $\{1,c_2,c_3\}$ with $1\lt c_2\lt c_3$ is "non-canonical" (meaning the greedy algorithm is sub-optimal) if and only if $0\lt r\lt c_2-q$, where $c_3=qc_2+r$ with $0\le r\lt c_2$.

Thus $\{1,7,10\}$ is non-canonical because $q=1$ and $r=3$ (i.e., $10=1\cdot7+3$) and $0\lt3\lt7-1$.

On the other hand, $\{1,4,7\}$ is canonical because $7=1\cdot4+3$ implies $q=1$ and $r=3$ and the condition $0\lt r\lt c_2-q$ does not hold since $3$ is not less than $4-1$.

The other two sets can be handled similarly. It's just a matter of working out the $q$ and $r$ for each set and checking that either $0=r$ or $r=c_2-q$.

$\endgroup$
5
  • $\begingroup$ Sorry Barry, would you please inspect other two sets? a litle confused :) $\endgroup$ Feb 13, 2016 at 21:20
  • $\begingroup$ Barry I need help on set {1,2,5} which value should be assign to Q? $\endgroup$ Feb 14, 2016 at 21:13
  • $\begingroup$ @user4249446, $q$ and $r$ are the quotient and remainder, respectively, when you divide the larger number $c_3$ by the smaller number $c_2$. So how many times does $2$ go into $5$, and with what remainder? $\endgroup$ Feb 15, 2016 at 1:41
  • $\begingroup$ for {1, 2, 5} we get 5=1.2+3 ? am I right? $\endgroup$ Feb 15, 2016 at 7:59
  • $\begingroup$ @user4249446, when doing division, the remainder is always smaller than the number you're dividing by -- that's what Theorem 4 means when it says "with $0\le r\lt c_2$." When you write $5=1\cdot2+3$, you are getting a "remainder" of $3$, which is not less than $2$. $\endgroup$ Feb 15, 2016 at 12:30

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.