動態規劃：任務每一天，安排了最大利潤

有一組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

動態規劃：任務每一天，安排了最大利潤

回答

相關問題