如何爲以下設計動態規劃算法

我們有n個郵票，每個郵票我有一個特定的面額d（i）和大小s（i）。所有教派都是獨特的，我們可以多次使用郵票名稱。現在我想設計一個算法，用給定的d（i）和s（i）來計算郵票和郵資金額p，找到其面值恰好與p相加的郵票的最小總尺寸。如何爲以下設計動態規劃算法

我知道這是一個動態規劃問題，我也覺得它是像揹包問題一樣解決。但我完全感到困惑，因爲這裏郵票的最小總大小應該合計爲p。我想出了以下復發，我知道這不會是真實的，因爲它不檢查，如果總分大小加起來號碼：

M(p)=min{M(p-d(i))}+s(i),M(p-d(i))} for i from 1 to n

此外，我不知道如何製表那（以爲了編寫動態編程的迭代版本）。

我的猜測是我必須有一個尺寸爲p和d（i）的二維數組，並且每個單元格都填充了s（i）。

來源

2014-03-28 Hamed Minaee

以下是包含這兩個要求的DP再現關係。首先你的問題類似於揹包問題只有你需要填充揹包的變化，這裏的容量是p，(s(i),d(i))是物品的類型。

DP的解決方案： -

考慮有n項目進行(s(i),d(i))和郵資量p，Valid(n,p)表明，子問題都有解決方案，正是加起來p： -

DP(n,p) = 0; 
Valid(n,p) = 0; 

if(Valid(n-1,p)) { 

    DP(n,p) = DP(n-1,p); 
    Valid(n,p) = true; 

} 

if(Valid(n,p-d(n))) { 

    DP(n,p) = min{DP(n,p),DP(n,p-d(n)) + s(n)}; 
    Valid(n,p) = true; 

}

決賽結果：

if(Valid(n,p)) { 

    return(DP(n,p)); 

} 

else printf("no solution");

012採用自下而上

DP的解決方案： -

Valid[n][p+1] = {false}; 
DP[n][p+1] = {0}; 
Valid[0][0] = true; 
DP[0][0] = 0; 
for(int i=0;i<=p;i++) { 

    if(s[0]<=i) { 
     if(Valid[0][i-d[0]]) { 

     DP[0][i] = s[0] + DP[0][i-d[0]]; 
     if(s[0]==i) 
     Valid[0][i] = true; 
     }   
    } 
} 

for(int j=0;j<n;j++) 
    Valid[j][0] = true; 

for(int j=1;j<n;j++) { 

for(int k=1;k<=p;k++) { 

    if(Valid[j-1][k]) { 

     DP[j][k] = DP[j-1][k]; 
     Valid[j][k] = true; 

    } 

    if(Valid[j][k-d(j)]) { 

     DP[j][k] = min{DP[j][k],DP[j][k-d(j)] + s[k]}; 
     Valid[j][k] = true; 

    } 

} 

}

來源

2014-03-28 04:22:05

非常感謝你也可以說算法的迭代版本？（這對我來說更容易理解）？ –

@HamedMinaee查看我的編輯 –

謝謝我認爲遞歸關係是：min（i，j）= min {m（i-1，j），m（i，j-Pi）+ Si; if j> = pi）但是我不知道如何添加檢查總值的條件加起來就是p。你有什麼想法？ –

你的猜測是正確的。這是二維DP問題。但在我們宣佈我們需要達到遞推公式之前，我們會看到該公式中有多少個字段是變化的。

在您的問題陳述中有兩件事：1）郵票大小需要最小化。 2）所有的郵票應加起來總和P.如果你是初學者不認爲DP自下而上。首先考慮遞歸方法，經過一些練習後應該變得容易思考。在這種情況下，讓我們說你知道N個郵票的解決方案。讓我們用M（d（N），P）表示這種解決方案，它表示M是N個郵票中的總和爲P的解決方案。爲了得到遞歸關係，考慮如果最後一個郵票（Nth）不是結果的一部分，那麼問題將被縮小到找出N個N-1郵票中的P。如果存在最後一個元素（第N個郵票），問題是從N-1個郵票中找出P - d（N）總和。其中複發性關係看起來就像是：

M(N, P) = Min{ M(N-1, P), M(N-1, P - d(N))}

或更一般的意義：

M(i, P) = Min{ M(i - 1, P), M(i - 1, P - d(i))}

正如你可以看到兩個字段這個遞歸公式不同，因此你一定要認爲二維DP。

取兩軸，在X軸上取0到P所有總和，在y軸上取0到N（元素數）。迭代函數應該如下所示。

set all M(0, j) and M(i, 0) = 0 for all i [0, N] and j [0, P] 

for: i = 0 to N 
    for: j = 0 to P 
     for: int k = 0 to j 
     if: j - P(k) >= 0 and M(i, j) < M(i-1, j-P(k)) 
      M(i, j) = M(i-1, j-P(k)); 


return M(N, P);

注：因爲很明顯在併購這一領域將是一個需要最小化的選擇郵票大小我沒有提到的郵票大小。

來源

2014-03-28 08:58:28 user3401643

如何爲以下設計動態規劃算法

回答

相關問題