Dynamic Programming: Mission Per Day, Scheduling for Maximum Profit

Question

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 1

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

Answer 2

I would define the formula as following:

Let P(d,i):= on day d, you have consecutive worked for i days(including day d), the maximum dollars you can get

With base case P(1,1) = x_1, others to 0, then the answer is max(P(n,0), P(n,1)...P(n,5))

The formula is

P(d,0) = max(P(d-1,0), P(d-1,1)...P(d-1,5))
P(d,1) = P(d-1,0) + x_d
P(d,2) = P(d-1,1) + x_d
...
P(d,5) = P(d-1,4) + x_d

It obviously can be done with a single loop witch is O(n)

My reasoning of the formula is that, for P(d,i) where i>=1, it means you work on day d and as you consecutive work for i days already, the previous i-1 days you must be working as well, thus the formula P(d-1, i-1) + x_d

For P(d,0), it means you rest on day d, and you can rest on previous days as well, but for maximum of 5 days, otherwise it must not be the optimal solution (make sense?), thus the formula P(d,0) = max(P(d,i)) for i in [0,5]

Answer 3

Dynamically build a table of dimensions 6 x n. The entry table[w_i][d_j] will denote the maximal reachable value when Bob has worked for the last i days consecutively (including today) and it is day j.

The first column is easy to fill in: table[1][0] = x_0 if Bob decides to work on the first day, all other values are 0 (table[0][0] => Bob doesn't work on the first day, table[2..5][0] => Bob can't work for multiple consecutive days on day 1.)

Go on to complete the table column-by-column according to the following rules:

The maximum value on day j with 0 consecutive days of work is the maximum of any value of the previous day and not working today: table[0][d_j] = max{ table[0..5][d_j-1] }

The maximum value on day j with 1 consecutive day of work is the maximum of the previous 2 days with no consecutive days of work plus x_j. (It never makes sense to rest more than 2 days, as we could have just worked the day(s) in between.):

table[1][d_j] = max{ table[0][d_j-2], table[0][d_j-1] } + x[d_j]

Otherwise, table[w_i][d_j] = table[w_i-1][d_j-1] + x[d_j].

The solution will be the maximum value in the last column.

Answer 4

Each day i you have the choice of either working and reducing you remaining work days by 1 and profiting x_i or resting and resetting your available work days to 5, on the base case you are at day 0 with 5 consecutive work days available.

if (remaining_rest_days == 0) {
    MaximumProfit(current_day, 0, current_profit) = MaximumProfit(current_day+1, 5, current_profit)
} else {
    MaximumProfit(current_day, remaining_rest_days, current_profit) = 
    max(
        MaximumProfit(current_day+1, remaining_rest_days - 1, current_profits + profit[current_day]),
        MaximumProfit(current_day+1, 5, current_profits)
    )
}