A dynamic programming question...

Question

<< Ana needs to work on her algorithms homework, but the weather is getting nicer outside, so she also wants to spend more time outside.

Ana enjoys being outside more when

the weather is warmer: specifically, if the temperature outside is l (integer) units above zero,

Ana's happiness will increase by t after spending the day outside. (If L is negative, her happiness decreases.) On each of the n days until the homework is due, Ana will decide to either study or go outside (never both on the same day). To stay caught up with coursework, Ana creates a rule for herself that she will never go more than two days in a row without studying.

Given a weather forecast predicting the temperature 41, 2,..,In for the next n days, describe a worst-case On)-time dynamic programming algorithm to determine Ana's maximum possible happiness at the end of the n days. Briefly analyze your algorithm's running time.>>

Answer 1

Statement of Work

State of the current weather in temperature (tempO)

Time spent outside (oTime)

Time in days outside in a row (cNTotal).

Happiness level (t)

Days until homework is due (n).

study of not study (goOutside).

given weather as a list of integers per day (tempList).

dynamic programming an algorithm to calculate max happiness.

Questions: what is the unit on happiness, or is it defined as percent.

Given that happiness is a percentage of grade received / time stent outside.

Need more information about the relationship between study time and grade on homework. Given list of grades (grade) level based on study time as ((nTotal – oTtime) / nTotal) * 100.

Inputs                    

Total days until homework is due (nTotal).

given weather as a list of integers (list of temp / day).

Outputs

Happiness level (t).

Maximum possible happiness per n day period (tMax).

Algorithm

dynamic programming an algorithm to calculate max happiness.

tMax, tempO, oTime, cNTotal, t,  nTotal, TempList, goOutside, n

oTime =

if (tempO > 0) and not (temp  = < 0)  oTime + 1

or  

if not (tempO > 0) and (temp   < 0) oTime - 1;

t = if(outside is true) t + 1

nTotal = length of TempList

tMax =  (t  / nTotal   * 100) + (((nTotal – otime) / nTotal) * 100)

Solution pseudo code:

Initialize conditions.

If go outside is true, then happiness (t) increases per day.

If temperature outside (tempO) is above zero, then go outside.

If temp outside (tempO) is negative, then Happiness level (t) decreases.

Either go outside or study.

No more than 2 days without studying.

Determine max happiness (tMax)