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
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
