动态规划：每日任务，为最大利润进行调度

Question

问题：

Bob计划在一组n天内工作，在每一天i上都有一个任务；每个任务持续一天，必须在给定的第i天完成，Bob将获得xi美元报酬。Bob不能连续工作超过5个任务，在每5天至少需要休息一天。

已知数字x1...xn，哪些天应该让Bob执行任务，哪些天应该让他休息，以便尽可能赚取更多的钱而不超过5天工作？你的解决方案应该是O(n)。

我的问题：

我在想这个问题的递归公式时遇到了麻烦。我已经思考了很长时间，最初的想法是让p[i]=max{x_i + x_i-1 + ....+ x_i-4}，其中p[i]是从第i-4天到第i天可获得的最大利润。但是我意识到，首先，这并没有考虑到最优解可能有两个连续的工作日，其次，我没有建立在之前的解决方案之上。

我的问题是：有人能够帮我理解这个问题的结构吗？我觉得我只是没有理解会使解决方案容易看到的关键属性。

提前感谢！

- Jessa Marie

Answer 1

动态构建一个维度为6 x n的表格。条目table[w_i][d_j]表示当Bob连续工作了最后i天（包括今天）并且是第j天时，他能够达到的最大价值。

第一列很容易填写： 如果Bob决定在第一天工作，则table[1][0] = x_0，其他所有值都是0（table[0][0] => Bob在第一天不工作，table[2..5][0] => Bob不能在第一天连续工作多天）。

按照以下规则逐列完成表格：

当没有连续工作0天时，第j天的最大值是前一天的任何值和今天不工作的最大值：table[0][d_j] = max{ table[0..5][d_j-1] } 在有1个连续工作日的情况下，第j天的最大值是前两天没有连续工作日的最大值加上x_j。(休息超过2天从未有意义，因为我们可以在中间的一些天工作。)：

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

否则，table [w_i] [d_j] = table [w_i-1] [d_j-1] + x [d_j]。

解决方案将是最后一列中的最大值。

- Philip Becker

Answer 2

每天你都可以选择工作并将剩余工作天数减少1，获得收益x_i，或者休息并将可用工作天数重置为5。在基本情况下，你在第0天有5个连续的工作日可用。

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

- hbejgel

Answer 3

我将定义公式如下：

令 P(d,i):= 在第 d 天，你已经连续工作了 i 天（包括第 d 天），你能获得的最大收益为

基础情况为 P(1,1) = x_1，其余为 0， 然后答案为 max(P(n,0), P(n,1)...P(n,5))

该公式为

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

显然可以用单个循环来完成，时间复杂度为O(n)

我的推理公式是，对于P(d,i)，其中i>=1，它意味着你在第d天开始工作，并且连续工作了i天，前面的i-1天你也必须在工作，因此公式为P(d-1, i-1) + x_d

对于P(d,0)，它意味着你在第d天休息，并且之前几天你也可以休息，但最多只能休息5天，否则它就不是最优解（有道理吗？），因此公式为P(d,0) = max(P(d,i)) for i in [0,5]

- shole

Answer 4

我非常感激在这里发布的所有解决方案。我能够想出解决方案，所以我想发布它。请注意，此解决方案仅返回最大利润，而不是任何特定的日期。

让 P[i] = 如果 Bob 在第 i 天休息，则从第 1 天...i 的最大预期利润

递归：P[i] = max{p[j] + x_j+1 + x_j+2 + ... + x_i-1, for i - 6 <= j < i 因此，如果 Bob 在第 i 天休息，我们希望 P[i] 是他在最后五个连续工作日中工作的利润总和，加上他在最后一个休息日 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])
        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)

示例和结果

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

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

- Jessa Marie