Greedy algorithm proof

Question

There are 2n product and their prices: P={p_1, p_2, ..., p_2n}. When we buy the products in pairs we get the product with lower price for free.

I'm trying to prove formally that the following algorithm results in optimal solution:

1. Sort P from high to low.
2. Return the sorted prices as pairs.

This solution is pretty straightforward, however I'm having extremely difficult time proving it formally.

• Yuval Filmus: Perhaps you could share the solution with us, and we can help you make it more formal.

Answer 1

Let's assume that optimal answer is $A = \{(free_1, paid_1), ..., (free_n, paid_n)\}$ where $\forall i: free_i \le paid_i,ドル also sort this pairs by $paid,ドル i.e. $paid_1 \le paid_2 \le ... \le paid_n$.

I will use pairs to show products grouping - 1st product in pair I get for free, and for 2nd I need to pay.

If there is such $i$ that $paid_{i-1} > free_i,ドル take 2 pairs $(free_{i-1}, paid_{i-1}), (free_i, paid_i)$ (in this case we need to pay $paid_{i-1} + paid_{i}$) and swap prices:

1. In case $free_{i-1} \le free_i$ we got $(free_{i-1}, free_i), (paid_{i-1}, paid_i)$ (need to pay $free_i + paid_i$);
2. In case $free_{i-1} > free_i$ we got $(free_{i}, free_{i-1}), (paid_{i-1}, paid_i)$ (need to pay $free_{i-1} + paid_i$).

In both cases we don't do solution worse (we can not improve solution because we suppose that $A$ is optimal, but there is case that after swapping solution will not changed, e.g. $free_i < free_{i-1} = paid_{i-1} < paid_i$).

We have:

1. $paid_1 \le paid_2 \le ... \le paid_n,ドル that gives sorted sequence: $\{paid_1, paid_2, ..., paid_n\}$
2. $\forall i: paid_{i-1} \le free_i \le paid_i$ (more intuition: in sequence from p.1 we insert $free_i$ on appropriate places), that gives sorted sequence: $\{free_1, paid_1, free_2, paid_2, ..., free_n, paid_n\}$

So we show that optimal answer can be expressed in form of sorted array.