# greedy algorithms - minimizing total payment

The question:

I want to buy $n$ books. In the book store there's a big sale according to which, if you buy three books, then the cheapest book in any triplet costs only 20% of its full price. Let $c_1, c_2, …, c_n$ be the full price of the books you want to buy.

Suggest an algorithm for minimizing your total payment. Prove its optimality and analyze its time complexity.

My algorithm:

1. sort the prices of the books from big to small, such that $c_1 \ge c_2 \ge ... \ge c_n$ (change the locations of the books).
2. each book $c_i$ if $i \% 3 = 0$ then change its price to $c_i=0.2\cdot c_i$
3. return the sum of all books $\sum_{i=1}^nc_i$

Now, I'm having trouble proving that this is the optimal solution. I want to prove that if $i\%3=0$ for $c_i$, then I have a discount on this book.

I'm having a hard time formalizing the Greedy choice property. Given an optimal solution, what happens if $c_i$ such that $i\%3=0$ is not in the optimal solution? (doesn't have a discount)?

$c_1$ and $c_2$ cannot be the first reduced item. $c_1$ to $c_5$ cannot be the second reduced item. $c_1$ to $x_{299}$ cannot be the 100th reduced item. So using the groups $(c_1, c_2, c_3)$, $(c_4, c_5, c_6)$ etc. gives the optimal result.