[GAP Forum] (no subject)

[David Hobby]

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