Greedy Algorithm for license purchase problem

[Shaitan00]

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?

 

[wildman]

I think you left something out. Order doesn't seem to make any difference. Am I missing something?

 

[Shaitan00]

Of course order makes a difference.

Assume I have license 1 with rate t^3 and license 2 with rate 2^t - now these rates are exponential and there is no easy way to determine the correct growth rate (derivates are wrt to "t" as well), so how can you ensure you pick the right one first so that at (t+1) you don't end up having to spend more because license 2 now costs a lot more then license 1 would have?

So, depending on time (t) the price will be different, and seeing as all rates are different some things will become much more expensive then others as time goes on, those should be bought first.

 

[mathmate]

I am not sure if I understood the question properly, so I am expressing what I understand, and you can correct me if there is a misunderstanding.

" A company needs to buy n different software licences. The cost of license type j in month t from a given reference date is given by
C(j,t)=100*r(j)^t, j=1...n
where r(j) is the growth factor of the license of type j.
If the company can afford to buy 1 license per month, what is the optimal buying strategy in the choice of the order buying the n licences?
Assume that the company buys the first license at time t=0."

The objective is to minimise
Sum(C(j,t)) for t=0,n-1
by using a logical choice of j each month.
Since it is an exponential function, ASSUMING r(j)>1, its seems logical (to be verified) to use the inverse of the greedy algorithm, namely, pick the least expensive at time t=n-1, n-2, ... etc., i.e. pick the last one first. If r(j)<1, then it is logical to buy the least expensive each month as time goes on (t=0 to t=n-1).

 

[Shaitan00]

Nope - you pretty hit it right on...
That is what I was thinking also - start at month (n) - the last month - and calculate the rate, then choose the smallest one and buy it, and proced to month (n-1).

Thanks for the confirmation.
Much appreciated.