GessaGessa GessaGessa - 1 year ago 66
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

there is a mission; each mission lasts exactly one day, must be done on day
in which it is given, and pays bob
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.

, 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

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 Source

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


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])
            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