greedy algorithms - minimizing total payment

Question

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)?

Answer 1

This answer is a hint.

Assume an optimal solution exists. Order its choices so that they agree with your algorithm's choices for as long as possible; the order after this is unimportant. If all of them agree, then your algo picked an optimal solution, so you're done! If not, then at look at the first group of 3 where they disagreed. Even though you don't know exactly what an optimal solution is, you know that one exists, and you can make changes to it -- e.g. swapping some books in its ordering -- to produce a new solution.

Can you think of a way to change it in such a way that (a) it now agrees with your algo for 1 more group of 3 and (b) its score didn't get worse? If so, then clearly you could repeat this step until... What happens?

Answer 2

For every price-reduced item, you must have purchased two items at the same or higher price. Therefore, you cannot get one of the two highest priced items reduced, you cannot get two of the five highest priced items reduced, you cannot get 100 of the 299 highest priced items at a reduced price.

$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.