Details

A shop sells collectibles at prices $c_0,c_1,$dots,$c_{n-1}.$ You want to purchase all $n$ collectibles, but are only able to purchase one each month. Unfortunately, the price of each item doubles each month.

Give a greedy algorithm to minimize the total cost to purchase all $n$ items.

Prove that your greedy algorithm always outputs the optimal solution.