Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Coin sets
Replies: 6   Last Post: Jan 5, 2001 5:15 PM

 Messages: [ Previous | Next ]
 Hugo van der Sanden Posts: 234 Registered: 12/8/04
Re: Coin sets
Posted: Jan 5, 2001 11:57 AM

Arthur Meunier wrote:
>
> One interest of th usual coin sets is that if you follow a greedy algorithm
> you always obtain an optimal solution.
> Exemple with set {1,2,5,10} for 25
> 10 + 10 + 5 is optimal ( in number of coin )
> so if you always take the higher possible coin you obtain an optimal
> solution
> however if the set is {1,5,13,14} this algorithm would produce
> 14 + 1 + 1 + 1 +1 = 18;
> 13 + 5 = 18;
> find all the sets in P([1..n]) that always produce an optimal solution with
> a greedy algorithm.

I assume that we should only consider sets that include 1, since
otherwise not all numbers can be generated.

For the set A = { 1, a, b }, a < b, it is clear that the greedy solution
is not optimal for ka when b = ka - d, 0 <= d < a, and k - d <= 0. I
believe that this condition is also necessary for the 3-element set.
I've not yet looked in detail at larger sets.

Hugo

Date Subject Author
1/4/01 Arthur Meunier
1/5/01 Hugo van der Sanden
1/5/01 David Eppstein
1/5/01 Arthur Meunier
1/5/01 David Eppstein
1/5/01 Arthur Meunier
1/5/01 Arthur Meunier