机器人硬币收集 - 动态规划

机器人硬币收集问题机器人硬币收集 - 动态规划

若干硬币被放置在n × m板的细胞，无细胞每超过一个硬币。位于纸板左上角的机器人需要收集尽可能多的硬币，并将带到右下角的单元格。在每一步中，机器人都可以将一个单元移动到右侧，也可以从当前位置向下移动一个单元。当机器人用一枚硬币来访问一个单元格时，它总是拿起那枚硬币。设计一种算法来查找机器人可以收集的最大硬币数量以及它需要遵循的路径。

如果电路板上的某些单元不可用于机器人，您将如何修改硬币的动态编程算法收集问题？将你的算法应用到下面的板上，其中不可访问的单元由X显示。这块板有多少条最佳路径？

我编码上述图像，并且它的工作原理以及输出显示4.不可访问单元被标记为-1。但是，我使a[0][1]=1可访问，我得到一个奇怪的问题，其中显示a[1][0]=3初始化后，输出是6而不是5.如何显示单元格a[1][0]而不是1？无论我在a[0][1]更改哪些内容受到影响，我都会受到影响a[1][0]。那个怎么样？我哪里错了？

#include <stdio.h> 

int max(int a,int b) 
{ 
    return a>b?a:b; 
} 

int robot_coin_collect(int m,int n,int a[][n]) 
{ 
    int i=1,j=1,k,c[m][n]; 

    c[0][0]=a[0][0]; 
    while(a[i][0]!=-1) 
    { 
     c[i][0]=c[i-1][0]+a[i][0]; 
     i=i+1; 
    } 
    for(;i<m;i++) 
     c[i][0]=-6; 
    while(a[0][j]!=-1) 
    { 
     c[0][j]=c[0][j-1]+a[0][j]; 
     j=j+1; 
    } 
    for(;j<n;j++) 
     c[0][j]=-6; 

    display(m,n,c);  // after initialising 
    printf("\n\n"); 

    for(i=1;i<m;i++) 
    { 
     for(j=1;j<n;j++) 
     { 
      if(a[i][j]!=-1) 
       c[i][j]=max(c[i-1][j],c[i][j-1])+a[i][j]; 
      else 
       c[i][j]=-6; 
     } 
    } 

    display(m,n,c);  // after the algorithm finishes, result 
    return c[m-1][n-1]; 
} 

void display(int m,int n,int c[][n]) 
{ 
    int i,j; 

    for(i=0;i<m;i++) 
    { 
     for(j=0;j<n;j++) 
      printf("%d\t",c[i][j]); 
     printf("\n"); 
    } 
} 

int main(void) 
{ 
    int a[5][6]={0,1,0,1,0,0, 
       1,0,0,-1,1,0, 
       0,1,0,-1,1,0, 
       0,0,0,1,0,1, 
       -1,-1,-1,0,1,0}; 

    printf("%d",robot_coin_collect(5,6,a)); 
    return 0; 
}

来源

2016-07-24 build_code

而（A [0] [j]的！= - 1） { C [0] [j] = C [0] [j-1] + A [0] [j ]。 j = j + 1; } 当您使其可访问时，[0] [1]不是-1，增加极限界限条件 – mojtaba357

极限界限条件？像什么？我的意思是为什么'a [1] [0]'变化，对于在'a [0] [1]'处更改的值？ –

limit bound like： while（i mojtaba357

问题是你的代码可以修改内存，并且超出了数组边界的小区时，没有任何-1的第一行或第一列

中为什么没有这个奇怪运行时错误，你可以看到在while条件this link和this

附加约束限制：

while(i<m && a[i][0]!=-1) 
{ 
    c[i][0]=c[i-1][0]+a[i][0]; 
    i=i+1; 
}

和

while(j<n && a[0][j]!=-1) 
{ 
    c[0][j]=c[0][j-1]+a[0][j]; 
    j=j+1; 
}

来源

2016-07-24 19:14:16 mojtaba357

完全明白。仅仅因为数组是连续的内存块，在'j'超出'a [0] [j]'的数组边界之后，在[a] [1] [j]处的数组位置受到影响，直到遇到'a [1] [j]！= - 1'在位置'j = 3'。该链接帮助并感谢详细的解决方案。 –

并不总是取决于操作系统内存管理，以给出进程的哪个地址。我编辑答案有点检查，祝你好运。 – mojtaba357

int CoinCollecting(int c[][], int M[][],int i,int j){ 
    int Max(int a,int b) 
    { 
     return a>b?a:b; 
    } 
    if(i==0 || j==0) 
    { 
     M[i][j]=0; 
     return 0; 
    } 
    if(m[i-1][j]<0) 
    { 
     M[i-1][j]=CoinCollecting(c[][],M[][],i-1,j); 
    } 

if(m[i][j-1]<0) 
{ 
    M[i][j-1]=CoinCollecting(c[][],M[][],i,j-1); 
} 

M[i][j]=Max(M[i-1][j],M[i][j-1]+c[i][j]); 
return M[i][j] 
}

来源

2017-05-18 06:10:03

机器人硬币收集 - 动态规划

回答

相关问题