Question

Suppose we are managing a consulting team of expert computer hackers, and each week we have to choose a job for them to undertake. The set of possible jobs is divided into low-stress and high-stress jobs. If we select a low-stress job for the team in week i, then we get a revenue of li > 0 dollars; if we select a high-stress job, we get a revenue of hi > 0 dollars. The catch, is that in order for the team to take a high-stress job in week i, it is required that they do no job (of either type) in week i − 1; they need a full week of prep time to get ready for the crushing stress level. On the other hand, it is okay for them to take a low-stress job in week i even if they have done a job (of either type) in week i − 1. Given a sequence of n weeks, a plan is specified by a choice of "low-stress", "high-stress", or "none" for each of the n weeks, with the property that if "high-stress" is chosen for week i > 1, then none has to be chosen for week i − 1. (It is okay to choose a high-stress job in week 1.) The value of the plan is determined in the natural way: for each i, we add li to the value if we choose "low-stress" in week i, and we add hi to the value if we choose "high stress" in week i. (We add 0 if we choose "none" in week i.) Give an efficient algorithm that takes values for l1, l2, . . . , n and h1, h2, . . . , hn and returns the value of an optimal plan.

Answer 1

if number == 1

then

tempSolution= max(l[number],h[number])

else if number == 2 then

tempSolution= max(optimalPlan(1, l, h)+ l[2], h[2])

else

tempSolution= max(optimalPlan(number − 1, l, h) + l[number], optimalPlan(number − 2, l, h) + h[number])

end if

return Value

FindOptimalValue(number, l, h)

for itterator = 1 ! number do

tempSolution[itterator] = 0

end for

for itterator = 1 ! number do

if itterator == 1 then

tempSolution[itterator] max(l[itterator], h[itterator])

else if itterator == 2 then

tempSolution[itterator] max(tempSolution[1] + l[2], h[2])

else

tempSolution[itterator] max(tempSolution[itterator − 1] + l[itterator], tempSolution[itterator − 2] + h[itterator])

end if

end for

return Value[number]

OPtimalPlan(number, l, h, Value)

for itterator = 1 ! number do

WeekVal[itterator]

end for

if tempSolution[number] − l[number] = tempSolution[number − 1] then

WeekVal[number] ”Low stress”

OPtimalPlan(number-1, l, h, Value)

else

WeekVal[number] ”High stress”

OPtimalPlan(number-2, l, h, Value)

end if

return WeekVal