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




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; > 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 3element set. I've not yet looked in detail at larger sets.
Hugo



