需要帮助编写一般情况下的伪代码

我要开始辅导，所以我决定从算法类中处理一些旧问题。问题如下：您正在销售报纸，并且每天都在一个路口开始路线，并结束您的路线=您开始的东北部。城市街道在网格上，如下图所示，你从（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

需要帮助编写一般情况下的伪代码

回答

相关问题