[GAP Forum] (no subject)
David Hobby
hobbyd at newpaltz.edu
Sat Jan 3 00:45:32 GMT 2009
Nicoleta Gramisteanu wrote:
> Please give in your ideas and suggestions for best algorithm on the following problems :
>
> In a kiosk (a stand, sort of shop), they decided to make a discount
> if you buy two products, the cheaper is for free
> we have 2n products with prices p1, p2, ..., p2n
> order products in pair that the total cost amount is minimized
Nicoleta--
Hi. Maybe I misunderstand the problem.
It seems like the best algorithm is
"put them in linear order by price, and
then pair up adjacent ones". I believe
there's an easy proof by induction on n
that that gives an optimal set of pairs.
Or please give a counter-example?
---David
More information about the Forum
mailing list