需要幫助編寫一般情況下的僞代碼

我要開始輔導，所以我決定從算法類中處理一些舊問題。問題如下：您正在銷售報紙，並且每天都在一個路口開始路線，並結束您的路線=您開始的東北部。城市街道在網格上，如下圖所示，你從（0，0）開始到（n，m）結束。向北移動將您從（x，y）移至（x，y +1）。東移讓你從（x，y）到（x + 1，y）。在每個路口（x，y），您停下來銷售報紙，並且收入r（x，y）的收入。設OPT（n，m）表示從（0,0）到（n，m）的最佳步行總收入。需要幫助編寫一般情況下的僞代碼

我使用自下而上動態編程針對此問題的僞代碼如下所示：

Bottom-Up-Alg(n,m,s[][]) \\ n and m are coordinates and s holds the revenue at each coordinate (n,m) 
opt = 0  \\ holds optimal revenue 
opt += s[0][0] \\value at (0,0) 
i = 0 
j = 0 
while (i <= n and j <= m) 
    if (s[i+1][j] > s[i][j+1]) 
     opt += s[i+1][j] \\ Move east 
     i++ 
    else 
     opt += s[i][j+1]  \\ Move north 
     j++ 
return r

嚴格地說該算法的運行時間將是O（N + M）。但是，如果n和m成比例，則運行時間可以被認爲是O（n）或O（m）。

問題是，我發現我的算法是貪婪的，它不會適用於所有情況。我在編寫僞代碼時會遇到麻煩，這一般會起作用。幫助將不勝感激。如果你能給我任何你想出的解決方案的運行時間，那也是很好的。

來源

2014-11-05 user101279

你可以編號的每一個節點，從右上方節點開始，你可以得到最大的收益，如果你從這個節點開始，這在先節點賦予它是最大的。 O（納米）。

可以通過從右上方席捲一對角線左下做到這一點。

當該編號到達左下角，你有你的答案。只需追溯到。

22 19-17-15--9 
    | 
27 26 17 16 14 
    | 
35-32 22 22 20

增加：如果你想知道如何掃描一個對角線，它比代碼更容易可視化。 enter image description here

但這裏的一些C：

for (j = m-1; j >= -(n-1); j--){ 
    for (ii = n-1; ii >= 0; ii--){ 
    int jj = j + (n-1) - ii; 
    int rii = rjj = 0; 
    if (jj >= 0 && jj < m){ 
     if (ii+1 < n && jj >= 0 && jj < m) 
     rii = r[ii+1][jj]; 
     if (jj+1 < m && jj+1 >= 0) 
     rjj = r[ii][jj+1]; 
     r[ii][jj] = s[ii][jj] + max(rii, rjj); 
    } 
    } 
}

基本上ii和jj是你的工作對細胞的指標，如果任其向右或向上的鄰居是你把矩形之外的收入爲零。

來源

2014-11-05 16:39:35

你的算法工作，因爲它就像Dijkstra算法，但發現在向非循環圖，其中每個節點具有兩個有向邊的最長路徑。該算法以貪婪的方式找到關鍵路徑。

的運行時間應該是O（MN）。這就像編輯距離的追溯程序。

來源

2014-11-05 17:44:45 sereneL

這是你的助教。我不禁注意到，這個問題是在你作業的截止日期之前發佈的。看到現在已經過去，你要找的答案如下

BOTTOM-UP-NEWSPAPER(n,m,r) 
    opt = array(n,m) 
    for i = 0 to n 
    for j = 0 to m 
     if i = 0 and j = 0  // In starting position 
     opt[i][j] = r(i,j) 
     else if i = 0 and j > 0 // On the south side of grid 
     opt[i][j] = r(i,j) + opt[i][j-1] 
     else if j = 0 and i > 0 // On the west side of grid 
     opt[i][j] = r(i,j) + opt[i-1][j] 
     else     // Anywhere else 
     opt[i][j] = r(i,j) + max(opt[i-1][j], opt[i][j-1]) 
    opt[n][m] holds the maximum revenue

來源

2014-11-06 05:22:08

我很尷尬，我沒有認識到這是作業。抱歉。 – 2014-11-06 13:43:55

需要幫助編寫一般情況下的僞代碼

回答

相關問題