The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Hugo van der Sanden

Posts: 234
Registered: 12/8/04
Re: Coin sets
Posted: Jan 5, 2001 11:57 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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;
> instead of
> 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.


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.