GessaGessa - 5 months ago 15x
Python Question

# Dynamic Programming: Mission Per Day, Scheduling for Maximum Profit

The problem:

There is a set of n days that Bob is planning to work, and on each day

`i`
there is a mission; each mission lasts exactly one day, must be done on day
`i`
in which it is given, and pays bob
`x_i`
dollars. Bob cannot work more than 5 consecutive missions at a time. That is, he must take at least 1 rest day every 5 days.

`Given`
numbers
`x_1...x_n`
, on which days should Bob perform missions, and on which days should he rest, in order to make as much money as possible and not work more than 5 days? Your solution should be
`O(n)`

My issue:

I am having trouble coming up with the recurrence for this problem. I have been thinking about this problem for a long time. My original thought was to let
`p[i] = max{x_i + x_i-1 + .... + x_i-4}, where p[i] is the max profit earnable from days i-4 to i.`
However, I realize, one, that this does take in to account that the optimal solution might have two consecutive work days, and two, I am not building off previous solutions.

My Question: Can anyone give me insight on understanding the structure of this problem? I feel like I am just not understanding the key properties that would make the solution easy to see.

I really am grateful for all the solutions posted here. I was able to come up with the solution, so I thought I would post it. Note that this solution only returns the maximum profit, not any specific days.

`Let P[i] = the maximum expected profit from day 1...i if Bob rests on day i`

`Recurrence: P[i] = max{p[j] + x_j+1 + x_j+2 + ... + x_i-1, for i - 6 <= j < i` Thus, we want `P[i]` to be the sum of the last five consecutive days that bob would have worked if he rests on day `i`, plus the profit he would have made by the last rest day `j`

Code:

``````def get_best_missions(x):

n = len(x)

p = [0 for i in range(n)]

for i in range(1,n):
j = i - 6

if j < 0:
p[i] = sum(x[0:i])
else:
p[i] = max(p[i], p[j] + x[j+1] + x[j+2] + x[j+3] + x[j+4] + x[i - 1])

return max(p)
``````

Example & Results

``````x = [10, 10, 10, 5, 20, 10, 5]
best = get_best_missions(x)

p = [0, 10, 20, 30, 35, 55, 55]
best = 55
``````