GessaGessa GessaGessa - 6 months ago 29
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.

Thanks in advance!

Answer

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