Dynamic Programming Algorithm (MinCost buying Apples)

2
votes

Hello I am trying to build a dynamic programming solution for the following problem :

Given that a family consumes 2kg of apples per day, the apples last 10 days and the price of the kg of apples per day on day i is p[i] , I have to find the minimum cost so the family does not run out of apples .

Without the 10 days limit i have come up with the solution , that i make a new array :

locmin=p[1]
for i=2 to n 
if locmin>=p[i] then c[i]=p[i]
else locmin=p[i] c[i]=p[i]
and then 
OPT[1]=c[i]
OPT(i)=OPT[i-1]+2*c[i] (well not so much of dynamic programming but it is O(n)) .

When putting 10 days limitation into account i come up with with a c[i,10] matrix where i store the lowest values of previous 10 days window the same manner as before for every i-10,i and come up with the solution 

OPT(i)=OPT[i-1]+2*min(p[i,j]) 0<j<=10

. O(n^2) solution Any ideas ?

1
algorithmdynamic-programming
your second solution's complexity is 10*n which is O(n) – DPDP
Yes i just realized later since 10 days is a constant – Akismpa
"Any ideas" is a quite broad question. Is there still a (specific) question? – trincot

1 Answers

0
votes

We can do O(n) not just for 10 days but for an arbitrary sized window. Let's take one day at a time. Each day, the family eats 2kg of apples. What's the price of only these two kg? Clearly, it's 2 * best_price, where best_price = min(p[i-9...i]).

Let's keep a stack. If a price is higher we add to the stack, if it's lower, we pop the stack till a lower earlier price or the stack is empty, then add the new price. The first element in the stack will be the best choice, and it will get replaced by the next element in the stack when it expires.