我如何解決這個動態編程？

我正在練習DP，我遇到了這個問題。 http://www.spoj.com/problems/MPILOT/en/我如何解決這個動態編程？

查理收購了航空運輸公司，並留在業務上，他需要通過任何可能的方式降低費用。有N個飛行員爲他的公司工作（N是偶數），需要製造N/2架飛機機組。飛機機組由兩名飛行員組成 - 一名機長和他的助手。隊長必須比他的助手年長。每個飛行員都有一份合同給他兩種可能的薪水 - 一個是船長，另一個是助理。對於同一名飛行員，隊長的薪水大於助理的薪水。但是，有可能助理的薪水比他的隊長高。編寫一個程序，計算查理需要爲飛行員的工資支付的最低金額，如果他決定花費一些時間在機組人員中做出最優化（即最便宜的）飛行員安排。

輸入

輸入的第一行包含整數N，2≤N≤10,000，n爲偶數，努力爲查理的公司飛行員的數量。接下來的N行輸入包含飛行員的薪水。這些生產線按照飛行員的年齡分類，最年輕的飛行員的工資是第一名。這N行中的每一行都包含由空格字符X i Y，1≤Y < X≤100,000，作爲上尉（X）的薪水和作爲助理（Y）的工資分隔的兩個整數。

輸出

輸出應該包含貨幣少量查理需要給的飛行員薪水的第一個也是唯一行。

經過研究，我發現這將通過DP解決，但我究竟如何解決這個問題？我花了幾個小時閱讀鏈接，但我沒有得到一個很容易理解的鏈接。請幫幫我。

來源

2015-11-07 Harry Lewis

索取spoj解決方案有點不對勁。但是我知道什麼。 –

事情是，我真的很難解決它，甚至想出了一個復發，但它沒有給出正確的答案。我不知道那裏出了什麼問題。如果我的邏輯是不正確的或其他的，最後我在這裏發佈它。我也不這樣做，但請幫助我這個。這將非常感激。謝謝！ :) –

像往常一樣，我們需要找到一組緊湊的子問題。記住飛行員如何匹配的細節不會做 - 我們需要類似以下特徵的東西。

考慮使每個飛行員成爲船長或助理而不考慮匹配的標籤。當且僅當以下兩個條件成立時才存在有效的匹配：

有N/2名隊長和N/2助理。
對於每個年齡段的截止日期，至少有比截止年齡小的助理，因爲有比隊長年齡小的隊長。

「唯一的」方向很容易：條件1是顯而易見的，條件2成立，因爲不等式對每個2飛行員都是成立的，我們可以對這些不等式進行求和。

對於「如果」方向，我們實際上必須建造船員。我們通過歸納進行。如果沒有飛行員，則空比賽是有效的。否則，由於最年輕的飛行員是助理（通過條件2）並且至少存在一名機長（通過條件1），因此存在（通過Sperner的引理，如果你想要看上去）一對飛行員，使得（a）否飛行員年齡中等（b）年齡較小者爲助理（c）年齡較大者爲隊長。匹配這一對並將它們從池中移除。觀察到兩個條件仍然成立，所以通過歸納假設來匹配其餘條件。

這個觀察導致一個O（N^2）時間動態程序。我們反覆閱讀下一個最老的飛行員的薪水，然後計算，考慮到K飛行員已被考慮到目前爲止，所有的C從0到[K/2]，支付K - C助手和C船長的最低費用飛行員。最後，返還支付N/2助理和N/2上尉的費用。未經測試的Python：

def cost(pilots): 
    cost = [0] 
    for i, (assistant_salary, captain_salary) in enumerate(pilots): 
     cost.append(float('inf')) # two-way sentinel 
     cost = [min(cost[c] + assistant_salary, 
        cost[c - 1] + captain_salary) 
       for c in range((i + 1)/2 + 1)] 
    return cost[-1] # i.e., N/2

來源

2015-11-07 17:39:25

讓我們給出遞歸的一些條件：如果我們已經達到最後，返回總和;如果我們有N/2助理，請加上隊長;如果我們的助理人數與剩下的隊長數量相同，那麼接下來增加一名助理（我們不能有比助理小的隊長）;否則，返回添加隊長或助理的最低成本。

JavaScript代碼：

var x = [4,5,6,7]; 
var y = [3,2,1,2]; 
var n = x.length; 

function f(i,ys,s){ 
    if (i == n){ 
    return s; 
    } 
    if (ys == n/2){ 
    return f(i + 1,ys,s + x[i]); 
    } else if (i % 2 == 0 && ys == i/2){ 
    return f(i + 1,ys + 1,s + y[i]); 
    } else { 
    return Math.min(f(i + 1,ys + 1,s + y[i]),f(i + 1,ys,s + x[i])); 
    } 
}

輸出：

console.log(f(0,0,0)) // 16

來源

2015-11-07 21:37:09

實際上，有想象它一個很好的方式。從左下角開始我們的升序列表中，我們可以設想選擇Y（助理的薪水）作爲向右移動和X（上尉的薪水）作爲向上移動，條件是西南 - 東北對角線沒有交叉（參見Wikipedia中的Catalan Number）。

從這裏我們可以看到，在三角形的每個節點最多有兩位前輩，從西部或南部，所以自下而上一般情況下應該是：

    captain    assistant 
dp[i][j] = min(x[i+j-1] + dp[i-1][j], y[i+j-1] + dp[i][j-1]) 

Example: 

x = [4,5,6,7] 
y = [3,2,1,2] 

      [9+7] 
    [3+5] [min(8+1,5+6)] 
[.] [3] [3+2]

我會留下編碼作爲練習。

來源

2015-11-08 23:27:53

我如何解決這個動態編程？

回答

相關問題