Greedy Algorithm for license purchase problem
Your friends are starting a security company that needs to obtain licenses for
n different pieces of cryptographic software. Due to regulations, they can only obtain these licenses at the rate of at most one per month.
Each license is currently selling for a price of $100. However, they are all becoming more expensive according to exponential growth curves: in particular, the cost of license j increases by a factor of rj > 1 each month, where rj is a given parameter. This means that if license j is purchased t months from now, it will cost 100×rtj . We will assume that all the price growth rates are distinct.
The question is: Given that the company can only buy at most one license a month, in which order should it buy the licenses so that the total amount of money it spends is as small as possible?