动态规划：任务每一天，安排了最大利润

有一组n天鲍勃计划工作，并在每个i天有一个使命;每个任务持续正好一天，必须在它给出的日期i完成，并支付鲍勃x_i美元。鲍勃一次不能连续执行超过5次任务。也就是说，他必须每5天至少休息一天。

Given号码x_1...x_n，在哪些日子里鲍勃应该执行任务，并在哪些日子里休息一下，以便尽可能赚到更多的钱并且不超过5天？您的解决方案应该是O(n)

我的问题：

我有想出复发这个问题烦恼。我一直在思考这个问题很长时间。我原先的想法是让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.但是，我意识到，其中一个，这确实考虑到最佳解决方案可能有两个连续的工作日，两个，我没有构建以前的解决方案。

我的问题：任何人都可以给我洞察力，了解这个问题的结构吗？我觉得我只是不理解将使解决方案易于看到的关键属性。

在此先感谢！

来源

2016-05-17 GessaGessa

我真的很感谢所有在这里发布的解决方案。我能够想出解决方案，所以我想我会发布它。请注意，此解决方案仅返回最大利润，并非特定日期。

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因此，我们要P[i]是最后连续五天鲍勃如果他停留在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

来源

2016-05-21 00:36:00 GessaGessa

每天我都可以选择工作并减少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) 
    ) 
}

来源

2016-05-17 15:43:25 hbejgel

动态构建尺寸表6 x n。条目table[w_i][d_j]将表示当鲍勃连续工作了最后的i天（包括今天）并且它是第j天时的最大可达值。

第一列是容易填写： table[1][0] = x_0如果Bob决定在上班的第一天，所有其他值都0（table[0][0] =>鲍勃不会在上班的第一天，table[2..5][0] =>鲍勃可以”

上j天最大值与工作0连续几天就是：为第1天）

去吧根据以下规则，完成表列逐列多个连续天T工作前一天的任何价值的最大值，今天不工作： table[0][d_j] = max{ table[0..5][d_j-1] }

与工作连续1天j天最大值是最大的前2天，工作加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]。

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

来源

2016-05-17 15:48:13

我会定义公式如下：

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

来源

2016-05-18 03:38:12 shole

动态规划：任务每一天，安排了最大利润

回答

相关问题